一、经验总结
在分析dp问题的状态表示时，发现当前阶段的状态可以继续细分为多个状态，且多个状态之间可以通过某种方式进行转换，这就是动态规划的多状态问题。
多状态问题的关键有以下几点：
-
找出dp问题的多个状态表示：经验+题目要求，在之前经验的基础上（以i位置为起点或终点）继续对当前阶段的状态进行细分。为每种状态各自创建出一个dp表。每种状态可能还有若干子状态，此时应该为每种状态的dp表增加维度，以表示出所有的子状态。
-
确定多个状态间的相互转换关系：对于简单题目可以直接得到转换关系（前4题）；但是如果每个阶段的状态数量较多，状态间的相互转换较为复杂，可以借助状态机模型分析各状态间的转换关系（后4题），其中：
- 各顶点表示的是每个阶段的各种状态（在第一步确定状态表示时得出）
- 箭头的起点是前一阶段的状态
- 箭头的终点是当前阶段的状态
- 箭头上的动作是状态转换时需要进行的活动（当前阶段）
如何绘制状态机？
- 先画出每个阶段的各种状态
- 对于每种状态，先考虑自己能不能转换为自己（状态不改变）
- 再考虑其他状态能不能转换为该状态
- 标出状态转换时需要进行的活动（也可以啥也不干）
-
之后就可以依据转换关系写出各种状态的状态转移方程了。最好依据绘制状态机的顺序写方程，做到不重不漏的计算出所有状态的结果。
-
填表顺序：要按照顺序将创建的多个dp表一起填
-
返回值：要考虑到所有的状态
二、相关编程题
2.1 按摩师
题目链接
面试题 17.16. 按摩师 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public:
int massage(vector<int>& nums) {
//1.创建dp表
//2.初始化
//3.填表
//4.返回值
int n = nums.size();
if(n == 0) return 0;
vector<int> dp1(n), dp2(n);
dp1[0] = nums[0];
for(int i = 1; i < n; ++i)
{
dp1[i] = dp2[i-1] + nums[i];
dp2[i] = max(dp1[i-1], dp2[i-1]);
}
return max(dp1[n-1], dp2[n-1]);
}
};
2.2 打家劫舍Ⅱ
题目链接
LCR 090. 打家劫舍 II - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
return max(rob1(nums, 2, n-1) + nums[0], rob1(nums, 1, n));
}
int rob1(vector<int>& nums, int begin, int end) {
if(begin >= end) return 0;
int n = end-begin; //左闭右开
vector<int> dp1(n), dp2(n); //dp1偷/dp2不偷
dp1[0] = nums[begin];
for(int i = 1; i < n; ++i)
{
dp1[i] = dp2[i-1] + nums[begin+i]; //注意下标映射关系
dp2[i] = max(dp1[i-1], dp2[i-1]);
}
return max(dp1[n-1], dp2[n-1]);
}
};
2.3 删除并获得点数
题目链接
740. 删除并获得点数 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 10001;
int arr[N] = {0}; //该数组用于统计每个数字出现的总和
for(auto e : nums)
arr[e]+=e;
vector<int> dp1(N), dp2(N); //dp1获取，dp2不获取
dp1[1] = arr[1];
for(int i = 2; i < N; ++i)
{
dp1[i] = dp2[i-1]+arr[i];
dp2[i] = max(dp1[i-1], dp2[i-1]);
}
return max(dp1[N-1], dp2[N-1]);
}
};
2.4 粉刷房子
题目链接
LCR 091. 粉刷房子 - 力扣（LeetCode）
题目描述
算法原理
编写代码
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]));
}
};
2.5 买卖股票的最佳时机含冷冻期
题目链接
309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
题目描述
算法原理
如果每个阶段的状态数量较多，状态间的相互转换较为复杂，可以借助状态机模型分析各状态间的转换关系，其中：
- 各顶点表示的是每个阶段的各种状态（在第一步确定状态表示时得出）
- 箭头的起点是前一阶段的状态
- 箭头的终点是当前阶段的状态
- 箭头上的动作是状态转换时需要进行的活动（当前阶段）
如何绘制状态机？
- 先画出每个阶段的各种状态
- 对于每种状态，先考虑自己能不能转换为自己（状态不改变）
- 再考虑其他状态能不能转换为该状态
- 标出状态转换时需要进行的活动
编写代码
class Solution {
public:
int maxProfit(vector<int>& p) {
int n = p.size();
vector<vector<int>> dp(n, vector<int>(3));
dp[0][0] = -p[0];
for(int i = 1; i < n; ++i)
{
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-p[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][2]);
dp[i][2] = dp[i-1][0]+p[i];
}
return max(dp[n-1][1], dp[n-1][2]);
}
};
2.6 买卖股票的最佳时机含手续费
题目链接
714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<int> f(n), g(n); //f是买入状态，g是可交易状态
f[0] = -prices[0];
for(int i = 1; i < n; ++i)
{
f[i] = max(f[i-1], g[i-1]-prices[i]);
g[i] = max(g[i-1], f[i-1]+prices[i]-fee);
}
return g[n-1]; //f[n-1]最后一天还有股票没有卖出，一定不是最大利润，不考虑
}
};
2.7 买卖股票的最佳时机III
题目链接
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
题目描述
算法原理
为什么INF（无穷大）用0x3f3f3f3f表示？请阅读文章：0x3f3f3f3f是什么意思-CSDN博客
用0x3f3f3f3f表示32-bit int最大值的好处：
- 足够大：0x3f3f3f3f是10^9级别的，比一般场合下的数据都要大，所以它可以作为无穷大使用，而不至于出现数据大于无穷大的情况。
- 加数据不会溢出：0x3f3f3f3f加上一个数据时并不会溢出，也就是说“无穷大加上一个有穷的数依然是无穷大”。甚至0x3f3f3f3f + 0x3f3f3f3f依然没有超过32-bit int的表示范围，也就满足了我们“无穷大加无穷大还是无穷大的需求”。
- 可以使用memset设置内存：之前如果我们要将某个int数组全部赋值为INT_MAX，需要自己写循环，不能使用memset，因为memset是以字节为单位进行赋值的。现在好了，如果我们将无穷大设为0x3f3f3f3f，由于它的每个字节都是0x3f，我们可以通过
memset(arr, 0x3f, sizeof(arr));将数组全部置为无穷大。
编写代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int INF = 0x3f3f3f3f; //无穷大
vector<vector<int>> f(n, vector<int>(3, -INF)), g(n, vector<int>(3, -INF));
//边界1：第0天第0次交易，其余交易次数的收益初始化为-∞
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]);
//边界2：第0次交易时卖出状态
if(j == 0)
g[i][j] = 0;
else
g[i][j] = max(g[i-1][j], f[i-1][j-1]+prices[i]);
}
}
return max(g[n-1][0], max(g[n-1][1], g[n-1][2]));
}
};
2.8 买卖股票的最佳时机Ⅳ
题目链接
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
题目描述
算法原理
编写代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
k = min(k, n/2); //n天最多进行n/2次有效交易
const int INF = 0x3f3f3f3f;
vector<vector<int>> f(n, vector<int>(k+1, -INF));
auto g = f;
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]);
if(j == 0)
g[i][j] = 0;
else
g[i][j] = max(g[i-1][j], f[i-1][j-1]+prices[i]);
}
}
int ret = -INF;
for(int j = 0; j <= k; ++j)
{
ret = max(ret, g[n-1][j]);
}
return ret;
}
};
