前言
大家好，我是jiantaoyab，开始刷动态规划的多状态类型相关的题目
动态规划5个步骤
- 状态表示 ：dp数组中每一个下标对应值的含义是什么>dp[i]表示什么
- 状态转移方程： dp[i] 等于什么
- 1 和 2 是动态规划的核心步骤，第三步是初始化，保证填表的时候不越界
- 填表顺序：为了保证填写当前状态的时候，所需要的状态已经计算过
- 返回值
按摩师
题目分析
- 初始化：f[i] = nums[0], g[i] = 0;
- 返回值：返回max(f[n - 1], g[n - 1]);
代码
class Solution {
public:
int massage(vector<int>& nums) {
if(nums.size() == 0) return 0;
int n = nums.size();
vector<int> f(n), g(n);
//初始化
f[0] = nums[0];
for(int i = 1; i < n; i++)
{
//选
f[i] = g[i - 1] + nums[i];
//不选
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n - 1], g[n - 1]);
}
};
打家劫舍II
题目分析
代码
class Solution {
public:
int rob1(vector<int>& nums, int l, int r)
{
if(l > r) return 0;
int n = nums.size();
vector<int> f(n), g(n);
//初始化
f[l] = nums[l];
for(int i = l + 1; i <= r; i++)
{
f[i] = g[i - 1] + nums[i];
g[i] = max(g[i - 1], f[i - 1]);
}
return max(f[r], g[r]);
}
int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
int n = nums.size();
//第一个位置选
int x = rob1(nums, 2, n - 2) + nums[0];
//第1个位置不选
int y = rob1(nums, 1, n - 1);
return max(x, y);
}
};
删除并获得点数
题目分析
f [i] : 到达 i 位置 nums[i] 选上，此时的最大点数
g [i] : 到达 i 位置 nums[i] 不选，此时的最大点数
初始化：f[0] = arr[0];
返回值：max(f[n - 1], g[n -1]);
代码
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 100001;
//预处理
sort(nums.begin(), nums.end());
int arr[N] = {0};
for(auto x : nums) arr[x] += x;
vector<int> f(N), g(N);
for(int i = 1; i < N; i++)
{
f[i] = g[i - 1] + arr[i];
g[i] = max(g[i - 1], f[i - 1]);
}
return max(f[N - 1], g[N - 1]);
}
};
粉刷房子
题目分析
**初始化：**新增加一个节点初始化为0
**填表顺序：**从左到右，3个表同时填
**返回值：**min(dp[n] [0],dp[n] [1],dp[n] [2]);
代码
class Solution {
public:
int minCost(vector<vector<int>>& costs) {
int n = costs.size();
vector<vector<int>> dp(n + 1, vector<int>(3));
for(int i = 1; i <= n; i++)
{
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
}
return min(dp[n][0], min(dp[n][1], dp[n][2]));
}
};
买卖股票的最佳时机含冷冻期
题目分析
**初始化：**dp[0] [0] = -prices[0]; dp[1] [0] = dp[2] [0] = 0;
返回值： max(dp[n - 1] [1], dp[n - 1] [2]);
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(3));
//初始化
dp[0][0] = -prices[0];
for(int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
dp[i][1] = dp[i - 1][0] + prices[i];
dp[i][2] = max(dp[i - 1][1], dp[i - 1][2] );
}
return max(dp[n - 1][1], dp[n - 1][2]);
}
};
买卖股票的最佳时机含手续费
题目分析
和上一道题目是类似的。
代码
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2));
//初始化
dp[0][0] = -prices[0] ;
for(int i = 1; i < n; i++)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i] );
dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i] - fee);
}
return dp[n - 1][1];
}
};
买卖股票的最佳时机 III
题目分析
这道题目的最大不同就是最多能完成2笔交易，就是可以0笔1笔2笔。
一般初始化负无穷的时候可以初始化为-0x3f3f3f3f。
**返回值：**返回g表最后一行的最大值
代码
class Solution {
const int INF = 0x3f3f3f3f;
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> f(n, vector<int>(3, -INF));
vector<vector<int>> g(n, vector<int>(3, -INF));
//初始化
f[0][0] = -prices[0], g[0][0] = 0;
for(int i = 1; i < n; i++)
{
for(int j = 0; j < 3; j++)
{
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
if(j - 1 >= 0)
g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
}
int ret = 0;
for(int j = 0; j < 3; j++)
ret = max(ret, g[n - 1][j]);
return ret;
}
};
买卖股票的最佳时机 IV
代码
和III的区别就是最大交易次数变成k,其他没什么区别。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
const int INF = 0x3f3f3f3f;
int n = prices.size();
k = min(k, n / 2); //k执行一半就行
vector<vector<int>> f(n, vector<int>(k + 1, -INF));
vector<vector<int>> g(n, vector<int>(k + 1, -INF));
//初始化
f[0][0] = -prices[0], g[0][0] = 0;
for(int i = 1; i < n; i++)
{
for(int j = 0; j <= k; j++)
{
f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
if(j - 1 >= 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
}
int ret = 0;
for(int j = 0; j <= k; j++)
ret = max(ret, g[n - 1][j]);
return ret;
}
};
