简单多状态 dp 问题（典型算法思想）—— OJ例题算法解析思路

目录

一、面试题 17.16. 按摩师 - 力扣（LeetCode）

算法代码：

代码思路解析：

问题分析：

动态规划定义：

状态转移方程：

初始化：

填表：

返回值：

优化空间复杂度：

二、213. 打家劫舍 II - 力扣（LeetCode） 

算法代码： 

代码思路解析：

1. 主函数 rob：

2. 辅助函数 rob1：

3. 状态转移方程：

4. 初始化：

5. 填表：

6. 返回结果：

优化空间复杂度：

总结：

三、740. 删除并获得点数 - 力扣（LeetCode） 

算法代码： 

代码思路解析：

1. 预处理：

2. 转化为“打家劫舍”问题：

3. 动态规划定义：

4. 状态转移方程：

5. 初始化：

6. 填表：

7. 返回结果：

优化空间复杂度：

总结：

四、 LCR 091. 粉刷房子 - 力扣（LeetCode）

方法一：算法代码（dp从1开始，costs从0开始）

索引对齐问题：

代码思路解析：

1. 问题分析：

2. 动态规划定义：

3. 状态转移方程：

4. 初始化：

5. 填表：

6. 返回结果：

优化空间复杂度：

总结：

方法二：算法代码（dp从0开始，costs也从0开始）

1. 从 0 开始的动态规划表：

2. 状态转移方程：

3. 初始化：

4. 为什么可以从 0 开始？

5. 举例说明：

6. 总结：

五、309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode） 

算法代码： 

代码思路解析：

1. 问题分析：

2. 动态规划定义：

3. 状态转移方程：

4. 初始化：

5. 填表：

6. 返回结果：

优化空间复杂度：

总结：

六、 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

算法代码：

代码思路解析：

1. 问题分析：

2. 动态规划定义：

3. 状态转移方程：

4. 初始化：

5. 填表：

6. 返回结果：

优化空间复杂度：

总结：

七、123. 买卖股票的最佳时机 III - 力扣（LeetCode） 

算法代码：

代码思路解析：

1. 问题分析：

2. 动态规划定义：

3. 状态转移方程：

4. 初始化：

5. 填表：

6. 返回结果：

优化空间复杂度：

总结：

八、 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

算法代码：

代码思路解析：

1. 问题分析：

2. 动态规划定义：

3. 状态转移方程：

4. 初始化：

5. 填表：

6. 返回结果：

优化空间复杂度：

总结：

 

---

一、面试题 17.16. 按摩师 - 力扣（LeetCode）

算法代码：

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if (n == 0)return 0; // 处理边界条件// 定义两个状态数组vector<int> f(n); // f[i] 表示选择第 i 个预约时的最大价值vector<int> g(n); // g[i] 表示不选择第 i 个预约时的最大价值// 初始化f[0] = nums[0];g[0] = 0;// 填表for (int i = 1; i < n; i++) {f[i] = g[i - 1] + nums[i]; // 选择第 i 个预约g[i] = max(f[i - 1], g[i - 1]); // 不选择第 i 个预约}// 返回最大值return max(f[n - 1], g[n - 1]);}
};

        这个代码实现了一个动态规划问题，通常被称为“按摩师问题”或“打家劫舍问题”。问题的核心是：给定一个数组 nums，表示每个预约的时长或价值，要求在不连续选择相邻元素的情况下，找到最大价值的组合。

代码思路解析：

1. 问题分析：

   • 每个元素 nums[i] 表示第 i 个预约的价值。

   • 不能选择相邻的预约，即如果选择了 nums[i]，就不能选择 nums[i-1] 和 nums[i+1]。

   • 目标是找到一种选择方式，使得总价值最大。

2. 动态规划定义：

   • 定义两个状态数组 f 和 g：

     • f[i] 表示选择第 i 个预约时的最大价值。

     • g[i] 表示不选择第 i 个预约时的最大价值。

   • 通过这两个状态数组，可以递推地计算出每一步的最优解。

3. 状态转移方程：

   • 如果选择第 i 个预约，那么前一个预约不能选择，因此 f[i] = g[i-1] + nums[i]。

   • 如果不选择第 i 个预约，那么前一个预约可以选择或不选择，取两者中的最大值，因此 g[i] = max(f[i-1], g[i-1])。

4. 初始化：

   • f[0] = nums[0]：如果只有一个预约，那么选择它的价值就是 nums[0]。

   • g[0] = 0：如果不选择第一个预约，那么价值为 0。

5. 填表：

   • 从 i = 1 开始，逐步计算 f[i] 和 g[i]，直到 i = n-1。

6. 返回值：

   • 最终的结果是 max(f[n-1], g[n-1])，即选择或不选择最后一个预约的最大价值。

优化空间复杂度：

当前的空间复杂度是 O(n)，可以通过滚动数组的方式优化到 O(1)：

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if (n == 0)return 0;int f = nums[0]; // 选择当前预约的最大价值int g = 0;       // 不选择当前预约的最大价值for (int i = 1; i < n; i++) {int new_f = g + nums[i]; // 选择当前预约int new_g = max(f, g);   // 不选择当前预约f = new_f;g = new_g;}return max(f, g);}
};

这个优化版本只使用了两个变量 f 和 g，空间复杂度降低到了 O(1)。

二、213. 打家劫舍 II - 力扣（LeetCode） 

算法代码： 

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;if (n == 1) return nums[0]; // 边界条件处理// 两种情况下的最大值return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}int rob1(vector<int>& nums, int left, int right) {if (left > right) return 0; // 边界条件处理int n = nums.size();vector<int> f(n); // f[i] 表示偷第 i 个房屋时的最大价值vector<int> g(n); // g[i] 表示不偷第 i 个房屋时的最大价值// 初始化f[left] = nums[left];g[left] = 0;// 填表for (int i = left + 1; i <= right; i++) {f[i] = g[i - 1] + nums[i]; // 偷第 i 个房屋g[i] = max(f[i - 1], g[i - 1]); // 不偷第 i 个房屋}// 返回结果return max(f[right], g[right]);}
};

        这个代码实现了一个动态规划问题，通常被称为“环形打家劫舍问题”。与普通的打家劫舍问题不同，这里的房屋是环形排列的，即第一个房屋和最后一个房屋是相邻的。因此，我们需要考虑两种情况：

1. 偷第一个房屋，但不能偷最后一个房屋。

2. 不偷第一个房屋，可以偷最后一个房屋。

最终的结果是这两种情况的最大值。

代码思路解析：

1. 主函数 rob：

• 首先检查数组的长度 n。

• 调用辅助函数 rob1 分别计算两种情况的最大值：

  • 情况 1：偷第一个房屋，但不能偷最后一个房屋。即 nums[0] + rob1(nums, 2, n - 2)。

  • 情况 2：不偷第一个房屋，可以偷最后一个房屋。即 rob1(nums, 1, n - 1)。

• 返回两种情况的最大值。

2. 辅助函数 rob1：

• 这个函数用于计算在给定区间 [left, right] 内偷取房屋的最大价值。

• 使用动态规划的思想，定义两个状态数组 f 和 g：

  • f[i] 表示偷第 i 个房屋时的最大价值。

  • g[i] 表示不偷第 i 个房屋时的最大价值。

• 通过状态转移方程逐步计算每个位置的最优解。

3. 状态转移方程：

• 如果偷第 i 个房屋，那么前一个房屋不能偷，因此 f[i] = g[i - 1] + nums[i]。

• 如果不偷第 i 个房屋，那么前一个房屋可以偷或不偷，取两者中的最大值，因此 g[i] = max(f[i - 1], g[i - 1])。

4. 初始化：

• f[left] = nums[left]：如果从 left 开始偷，那么偷第一个房屋的价值就是 nums[left]。

• g[left] = 0：如果不偷第一个房屋，那么价值为 0。

5. 填表：

• 从 left + 1 开始，逐步计算 f[i] 和 g[i]，直到 i = right。

6. 返回结果：

• 最终的结果是 max(f[right], g[right])，即偷或不偷最后一个房屋的最大价值。

优化空间复杂度：

当前的空间复杂度是 O(n)，可以通过滚动数组的方式优化到 O(1)：

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;if (n == 1) return nums[0]; // 边界条件处理// 两种情况下的最大值return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));}int rob1(vector<int>& nums, int left, int right) {if (left > right) return 0; // 边界条件处理int f = nums[left]; // 偷当前房屋的最大价值int g = 0;          // 不偷当前房屋的最大价值for (int i = left + 1; i <= right; i++) {int new_f = g + nums[i]; // 偷当前房屋int new_g = max(f, g);   // 不偷当前房屋f = new_f;g = new_g;}return max(f, g);}
};

总结：

• 主函数 rob 通过调用辅助函数 rob1 分别计算两种情况的最大值。

• 辅助函数 rob1 使用动态规划的思想，通过状态转移方程计算区间 [left, right] 内的最大价值。

• 通过滚动数组优化，空间复杂度从 O(n) 降低到 O(1)。

三、740. 删除并获得点数 - 力扣（LeetCode） 

算法代码： 

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001;// 1. 预处理int arr[N] = {0};for (auto x : nums)arr[x] += x;// 2. 在 arr 数组上，做一次“打家劫舍”问题// 创建 dp 表vector<int> f(N); // f[i] 表示选择第 i 个元素时的最大点数vector<int> g(N); // g[i] 表示不选择第 i 个元素时的最大点数// 填表for (int i = 1; i < N; i++) {f[i] = g[i - 1] + arr[i]; // 选择第 i 个元素g[i] = max(f[i - 1], g[i - 1]); // 不选择第 i 个元素}// 返回结果return max(f[N - 1], g[N - 1]);}
};

        这个代码实现了一个动态规划问题，通常被称为“删除并获得点数”问题。问题的核心是：给定一个整数数组 nums，你可以通过删除一个元素 nums[i] 来获得 nums[i] 的点数，但同时必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。目标是最大化获得的点数。

代码思路解析：

1. 预处理：

• 由于数组中的元素可能很大（最大为 10000），我们使用一个大小为 10001 的数组 arr 来统计每个数字的总点数。

• 遍历 nums，将每个数字 x 的点数累加到 arr[x] 中。例如，如果 nums = [2, 2, 3, 3, 3]，那么 arr[2] = 4，arr[3] = 9。

2. 转化为“打家劫舍”问题：

• 经过预处理后，问题转化为在 arr 数组上解决“打家劫舍”问题：

  • 不能选择相邻的元素（因为选择 arr[i] 意味着不能选择 arr[i-1] 和 arr[i+1]）。

  • 目标是最大化选择的元素的总和。

3. 动态规划定义：

• 定义两个状态数组 f 和 g：

  • f[i] 表示选择第 i 个元素时的最大点数。

  • g[i] 表示不选择第 i 个元素时的最大点数。

• 通过这两个状态数组，可以递推地计算出每一步的最优解。

4. 状态转移方程：

• 如果选择第 i 个元素，那么前一个元素不能选择，因此 f[i] = g[i - 1] + arr[i]。

• 如果不选择第 i 个元素，那么前一个元素可以选择或不选择，取两者中的最大值，因此 g[i] = max(f[i - 1], g[i - 1])。

5. 初始化：

• f[0] = 0 和 g[0] = 0，因为没有元素时点数为 0。

6. 填表：

• 从 i = 1 开始，逐步计算 f[i] 和 g[i]，直到 i = N - 1。

7. 返回结果：

• 最终的结果是 max(f[N - 1], g[N - 1])，即选择或不选择最后一个元素的最大点数。

优化空间复杂度：

当前的空间复杂度是 O(N)，其中 N = 10001。可以通过滚动数组的方式优化到 O(1)：

class Solution {
public:int deleteAndEarn(vector<int>& nums) {const int N = 10001;// 1. 预处理int arr[N] = {0};for (auto x : nums)arr[x] += x;// 2. 在 arr 数组上，做一次“打家劫舍”问题int f = 0; // 选择当前元素的最大点数int g = 0; // 不选择当前元素的最大点数for (int i = 1; i < N; i++) {int new_f = g + arr[i]; // 选择当前元素int new_g = max(f, g);  // 不选择当前元素f = new_f;g = new_g;}// 返回结果return max(f, g);}
};

总结：

• 通过预处理将问题转化为“打家劫舍”问题。

• 使用动态规划的思想，通过状态转移方程计算最大点数。

• 通过滚动数组优化，空间复杂度从 O(N) 降低到 O(1)。

四、 LCR 091. 粉刷房子 - 力扣（LeetCode）

方法一：算法代码（dp从1开始，costs从0开始）

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();// dp[i][j] 表示将第 i 个房子粉刷成第 j 种颜色时的最小总成本vector<vector<int>> dp(n + 1, vector<int>(3, 0));for (int i = 1; i <= n; i++) {// 选择颜色 0dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];// 选择颜色 1dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];// 选择颜色 2dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];}// 返回最后一个房子选择三种颜色中的最小总成本return min(dp[n][0], min(dp[n][1], dp[n][2]));}
};

索引对齐问题：

• 动态规划表 dp 的索引从 1 开始：

  • dp[i][j] 表示第 i 个房子粉刷成第 j 种颜色的最小成本。

  • i 的范围是 1 到 n，表示第 1 个房子到第 n 个房子。

• 输入数组 costs 的索引从 0 开始：

  • costs[k][j] 表示第 k 个房子粉刷成第 j 种颜色的成本。

  • k 的范围是 0 到 n-1，表示第 1 个房子到第 n 个房子。

因此，dp 表的第 i 个房子对应 costs 的第 i-1 个房子。

        这个代码实现了一个动态规划问题，通常被称为“粉刷房子”问题。问题的核心是：给定一个 n x 3 的二维数组 costs，其中 costs[i][j] 表示将第 i 个房子粉刷成第 j 种颜色的成本。要求相邻的房子不能粉刷成相同的颜色，求最小总成本。

代码思路解析：

1. 问题分析：

• 每个房子有三种颜色可选（假设为红、蓝、绿）。

• 相邻的房子不能选择相同的颜色。

• 目标是找到一种粉刷方案，使得总成本最小。

2. 动态规划定义：

• 定义 dp[i][j] 表示将第 i 个房子粉刷成第 j 种颜色时的最小总成本。

• j 的取值范围是 0、1、2，分别对应三种颜色。

3. 状态转移方程：

• 对于第 i 个房子，如果选择颜色 0，那么第 i-1 个房子只能选择颜色 1 或 2。因此：

  dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0];

• 如果选择颜色 1，那么第 i-1 个房子只能选择颜色 0 或 2。因此：

  dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1];

• 如果选择颜色 2，那么第 i-1 个房子只能选择颜色 0 或 1。因此：

  dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2];

4. 初始化：

• dp[0][0] = dp[0][1] = dp[0][2] = 0，表示没有房子时的成本为 0。

5. 填表：

• 从 i = 1 开始，逐步计算 dp[i][0]、dp[i][1] 和 dp[i][2]，直到 i = n。

6. 返回结果：

• 最终的结果是 min(dp[n][0], dp[n][1], dp[n][2])，即最后一个房子选择三种颜色中的最小总成本。

优化空间复杂度：

当前的空间复杂度是 O(n)，可以通过滚动数组的方式优化到 O(1)：

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();// 使用滚动数组优化空间复杂度int dp0 = 0, dp1 = 0, dp2 = 0; // 分别表示选择颜色 0、1、2 的最小成本for (int i = 1; i <= n; i++) {int new_dp0 = min(dp1, dp2) + costs[i - 1][0]; // 选择颜色 0int new_dp1 = min(dp0, dp2) + costs[i - 1][1]; // 选择颜色 1int new_dp2 = min(dp0, dp1) + costs[i - 1][2]; // 选择颜色 2dp0 = new_dp0;dp1 = new_dp1;dp2 = new_dp2;}// 返回最后一个房子选择三种颜色中的最小总成本return min(dp0, min(dp1, dp2));}
};

总结：

• 使用动态规划的思想，通过状态转移方程计算每个房子选择不同颜色的最小成本。

• 通过滚动数组优化，空间复杂度从 O(n) 降低到 O(1)。

• 最终结果是最后一个房子选择三种颜色中的最小总成本。

方法二：算法代码（dp从0开始，costs也从0开始）

class Solution {
public:int minCost(vector<vector<int>>& costs) {int n = costs.size();if (n == 0) return 0; // 边界条件处理// dp[i][j] 表示将第 i 个房子粉刷成第 j 种颜色时的最小总成本vector<vector<int>> dp(n, vector<int>(3));// 初始化第 0 个房子dp[0][0] = costs[0][0];dp[0][1] = costs[0][1];dp[0][2] = costs[0][2];// 填表for (int i = 1; i < n; i++) {dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]; // 选择颜色 0dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]; // 选择颜色 1dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]; // 选择颜色 2}// 返回最后一个房子选择三种颜色中的最小总成本return min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2]));}
};

1. 从 0 开始的动态规划表：

• dp[i][j] 表示第 i 个房子（索引从 0 开始）粉刷成第 j 种颜色的最小成本。

• 输入数组 costs 的索引也是从 0 开始，因此 dp[i][j] 直接对应 costs[i][j]。

---

2. 状态转移方程：

• 对于第 i 个房子（i >= 1）：

  • 如果选择颜色 0，则前一个房子不能选择颜色 0：

    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0];

  • 如果选择颜色 1，则前一个房子不能选择颜色 1：

    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1];

  • 如果选择颜色 2，则前一个房子不能选择颜色 2：

    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2];

---

3. 初始化：

• 对于第 0 个房子（i = 0）：

  • dp[0][0] = costs[0][0]：选择颜色 0 的成本。

  • dp[0][1] = costs[0][1]：选择颜色 1 的成本。

  • dp[0][2] = costs[0][2]：选择颜色 2 的成本。

---

4. 为什么可以从 0 开始？

• 从 0 开始的设计更符合数组的索引习惯，避免了 i - 1 的偏移。

• 初始化时直接使用 costs[0][j]，逻辑更直观。

• 动态规划表的索引与输入数组的索引完全一致，减少了出错的可能性。

---

5. 举例说明：

假设输入 costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]，表示有 3 个房子：

• costs[0] = [17, 2, 17]：第 0 个房子的三种颜色成本。

• costs[1] = [16, 16, 5]：第 1 个房子的三种颜色成本。

• costs[2] = [14, 3, 19]：第 2 个房子的三种颜色成本。

动态规划表的计算过程：

房子 (i)	dp[i][0] (颜色 0)	dp[i][1] (颜色 1)	dp[i][2] (颜色 2)
0	17	2	17
1	18 (2 + 16)	33 (17 + 16)	7 (2 + 5)
2	10 (7 + 3)	21 (18 + 3)	26 (18 + 19)

最终结果是 min(dp[2][0], dp[2][1], dp[2][2]) = min(10, 21, 26) = 10。

---

6. 总结：

• 动态规划表可以从 0 开始，只要正确处理索引对齐问题即可。

• 从 0 开始的设计更直观，避免了 i - 1 的偏移，逻辑更清晰。

• 两种实现方式（从 1 开始或从 0 开始）都是正确的，选择哪种方式取决于个人习惯和代码风格。

 

五、309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode） 

算法代码： 

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// dp[i][j] 表示第 i 天结束时处于状态 j 的最大利润vector<vector<int>> dp(n, vector<int>(3));// 初始化dp[0][0] = -prices[0]; // 第 0 天买入股票dp[0][1] = 0;          // 第 0 天不可能处于冷冻期dp[0][2] = 0;          // 第 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][2], dp[i - 1][1]);            // 不持有股票且不处于冷冻期}// 返回结果return max(dp[n - 1][1], dp[n - 1][2]);}
};

        这个代码实现了一个动态规划问题，通常被称为“股票买卖问题（含冷冻期）”。问题的核心是：给定一个股票价格数组 prices，你可以进行多次交易，但每次卖出股票后需要有一天的冷冻期（即不能立即买入）。目标是最大化利润。

代码思路解析：

1. 问题分析：

• 每天有三种状态：

  1. 持有股票（dp[i][0]）：表示第 i 天结束时持有股票的最大利润。

  2. 不持有股票且处于冷冻期（dp[i][1]）：表示第 i 天结束时没有股票，且处于冷冻期的最大利润。

  3. 不持有股票且不处于冷冻期（dp[i][2]）：表示第 i 天结束时没有股票，且不处于冷冻期的最大利润。

• 目标是找到最后一天的最大利润。

2. 动态规划定义：

• 定义 dp[i][j] 表示第 i 天结束时处于状态 j 的最大利润。

• j 的取值范围是 0、1、2，分别对应上述三种状态。

3. 状态转移方程：

• 持有股票（dp[i][0]）：

  • 可能是前一天就持有股票，即 dp[i-1][0]。

  • 也可能是今天买入股票，那么前一天必须是不持有股票且不处于冷冻期，即 dp[i-1][2] - prices[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][1] = dp[i-1][0] + prices[i];

• 不持有股票且不处于冷冻期（dp[i][2]）：

  • 可能是前一天就不持有股票且不处于冷冻期，即 dp[i-1][2]。

  • 也可能是前一天处于冷冻期，即 dp[i-1][1]。

  • 取两者的最大值：

    dp[i][2] = max(dp[i-1][2], dp[i-1][1]);

4. 初始化：

• 第 0 天（初始状态）：

  • dp[0][0] = -prices[0]：第 0 天买入股票，利润为 -prices[0]。

  • dp[0][1] = 0：第 0 天不可能处于冷冻期。

  • dp[0][2] = 0：第 0 天不持有股票且不处于冷冻期。

5. 填表：

• 从 i = 1 开始，逐步计算 dp[i][0]、dp[i][1] 和 dp[i][2]，直到 i = n-1。

6. 返回结果：

• 最终的结果是 max(dp[n-1][1], dp[n-1][2])，即最后一天不持有股票的最大利润（可能是冷冻期或非冷冻期）。

优化空间复杂度：

当前的空间复杂度是 O(n)，可以通过滚动数组的方式优化到 O(1)：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// 使用滚动数组优化空间复杂度int dp0 = -prices[0]; // 持有股票int dp1 = 0;          // 不持有股票且处于冷冻期int dp2 = 0;          // 不持有股票且不处于冷冻期for (int i = 1; i < n; i++) {int new_dp0 = max(dp0, dp2 - prices[i]); // 持有股票int new_dp1 = dp0 + prices[i];          // 不持有股票且处于冷冻期int new_dp2 = max(dp2, dp1);            // 不持有股票且不处于冷冻期dp0 = new_dp0;dp1 = new_dp1;dp2 = new_dp2;}// 返回结果return max(dp1, dp2);}
};

总结：

• 使用动态规划的思想，通过状态转移方程计算每天的最大利润。

• 通过滚动数组优化，空间复杂度从 O(n) 降低到 O(1)。

• 最终结果是最后一天不持有股票的最大利润（可能是冷冻期或非冷冻期）。

六、 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

算法代码：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// f[i] 表示第 i 天结束时持有股票的最大利润// g[i] 表示第 i 天结束时没有股票的最大利润vector<int> f(n);vector<int> g(n);// 初始化f[0] = -prices[0]; // 第 0 天买入股票g[0] = 0;          // 第 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];}
};

        这个代码实现了一个动态规划问题，通常被称为“股票买卖问题（含手续费）”。问题的核心是：给定一个股票价格数组 prices 和一个交易手续费 fee，你可以进行多次交易，但每次卖出股票时需要支付手续费。目标是最大化利润。

代码思路解析：

1. 问题分析：

• 每天有两种状态：

  1. 持有股票（f[i]）：表示第 i 天结束时持有股票的最大利润。

  2. 不持有股票（g[i]）：表示第 i 天结束时没有股票的最大利润。

• 目标是找到最后一天的最大利润。

2. 动态规划定义：

• 定义两个状态数组 f 和 g：

  • f[i] 表示第 i 天结束时持有股票的最大利润。

  • g[i] 表示第 i 天结束时没有股票的最大利润。

3. 状态转移方程：

• 持有股票（f[i]）：

  • 可能是前一天就持有股票，即 f[i-1]。

  • 也可能是今天买入股票，那么前一天必须没有股票，即 g[i-1] - prices[i]。

  • 取两者的最大值：

    f[i] = max(f[i-1], g[i-1] - prices[i]);

• 不持有股票（g[i]）：

  • 可能是前一天就没有股票，即 g[i-1]。

  • 也可能是今天卖出股票，那么前一天必须持有股票，即 f[i-1] + prices[i] - fee。

  • 取两者的最大值：

    g[i] = max(g[i-1], f[i-1] + prices[i] - fee);

4. 初始化：

• 第 0 天（初始状态）：

  • f[0] = -prices[0]：第 0 天买入股票，利润为 -prices[0]。

  • g[0] = 0：第 0 天不持有股票，利润为 0。

5. 填表：

• 从 i = 1 开始，逐步计算 f[i] 和 g[i]，直到 i = n-1。

6. 返回结果：

• 最终的结果是 g[n-1]，即最后一天不持有股票的最大利润。

优化空间复杂度：

当前的空间复杂度是 O(n)，可以通过滚动数组的方式优化到 O(1)：

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// 使用滚动数组优化空间复杂度int f = -prices[0]; // 持有股票int g = 0;          // 不持有股票for (int i = 1; i < n; i++) {int new_f = max(f, g - prices[i]); // 持有股票int new_g = max(g, f + prices[i] - fee); // 不持有股票f = new_f;g = new_g;}// 返回结果return g;}
};

总结：

• 使用动态规划的思想，通过状态转移方程计算每天的最大利润。

• 通过滚动数组优化，空间复杂度从 O(n) 降低到 O(1)。

• 最终结果是最后一天不持有股票的最大利润。

七、123. 买卖股票的最佳时机 III - 力扣（LeetCode） 

算法代码：

class Solution {
public:const int INF = 0x3f3f3f3f; // 表示无穷大int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// f[i][j] 表示第 i 天结束时，完成了 j 笔交易并持有股票的最大利润// g[i][j] 表示第 i 天结束时，完成了 j 笔交易并不持有股票的最大利润vector<vector<int>> f(n, vector<int>(3, -INF));vector<vector<int>> g(n, vector<int>(3, -INF));// 初始化f[0][0] = -prices[0]; // 第 0 天买入股票g[0][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) // 如果该状态存在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;}
};

        这个代码实现了一个动态规划问题，通常被称为“股票买卖问题（最多完成两笔交易）”。问题的核心是：给定一个股票价格数组 prices，你最多可以完成两笔交易（买入和卖出算一笔交易），目标是最大化利润。

代码思路解析：

1. 问题分析：

• 每天有两种状态：

  1. 持有股票（f[i][j]）：表示第 i 天结束时，完成了 j 笔交易并持有股票的最大利润。

  2. 不持有股票（g[i][j]）：表示第 i 天结束时，完成了 j 笔交易并不持有股票的最大利润。

• 目标是找到最后一天的最大利润。

2. 动态规划定义：

• 定义两个状态数组 f 和 g：

  • f[i][j] 表示第 i 天结束时，完成了 j 笔交易并持有股票的最大利润。

  • g[i][j] 表示第 i 天结束时，完成了 j 笔交易并不持有股票的最大利润。

• j 的取值范围是 0、1、2，表示完成的交易笔数。

3. 状态转移方程：

• 持有股票（f[i][j]）：

  • 可能是前一天就持有股票，即 f[i-1][j]。

  • 也可能是今天买入股票，那么前一天必须没有股票，即 g[i-1][j] - prices[i]。

  • 取两者的最大值：

    f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);

• 不持有股票（g[i][j]）：

  • 可能是前一天就没有股票，即 g[i-1][j]。

  • 也可能是今天卖出股票，那么前一天必须持有股票，且交易笔数增加 1，即 f[i-1][j-1] + prices[i]。

  • 取两者的最大值：

    g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);

4. 初始化：

• 第 0 天（初始状态）：

  • f[0][0] = -prices[0]：第 0 天买入股票，利润为 -prices[0]。

  • g[0][0] = 0：第 0 天不持有股票，利润为 0。

  • 其他状态初始化为 -INF（表示不可达状态）。

5. 填表：

• 从 i = 1 开始，逐步计算 f[i][j] 和 g[i][j]，直到 i = n-1。

6. 返回结果：

• 最终的结果是 max(g[n-1][0], g[n-1][1], g[n-1][2])，即最后一天不持有股票的最大利润。

优化空间复杂度：

当前的空间复杂度是 O(n)，可以通过滚动数组的方式优化到 O(1)：

class Solution {
public:const int INF = 0x3f3f3f3f; // 表示无穷大int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// 使用滚动数组优化空间复杂度vector<int> f(3, -INF); // 持有股票vector<int> g(3, -INF); // 不持有股票// 初始化f[0] = -prices[0]; // 第 0 天买入股票g[0] = 0;          // 第 0 天不持有股票// 填表for (int i = 1; i < n; i++) {vector<int> new_f(3, -INF);vector<int> new_g(3, -INF);for (int j = 0; j < 3; j++) {new_f[j] = max(f[j], g[j] - prices[i]); // 持有股票new_g[j] = g[j]; // 不持有股票if (j >= 1) // 如果该状态存在new_g[j] = max(new_g[j], f[j - 1] + prices[i]); // 卖出股票}f = new_f;g = new_g;}// 找到最后一行的最大值int ret = 0;for (int j = 0; j < 3; j++)ret = max(ret, g[j]);return ret;}
};

总结：

• 使用动态规划的思想，通过状态转移方程计算每天的最大利润。

• 通过滚动数组优化，空间复杂度从 O(n) 降低到 O(1)。

• 最终结果是最后一天不持有股票的最大利润（最多完成两笔交易）。

八、 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

算法代码：

class Solution {
public:const int INF = 0x3f3f3f3f; // 表示无穷大int maxProfit(int k, vector<int>& prices) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// 处理一个细节问题：最多只能完成 n/2 笔交易k = min(k, n / 2);// f[i][j] 表示第 i 天结束时，完成了 j 笔交易并持有股票的最大利润// g[i][j] 表示第 i 天结束时，完成了 j 笔交易并不持有股票的最大利润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]; // 第 0 天买入股票g[0][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) // 如果该状态存在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;}
};

        这个代码实现了一个动态规划问题，通常被称为“股票买卖问题（最多完成 k 笔交易）”。问题的核心是：给定一个股票价格数组 prices 和一个整数 k，你最多可以完成 k 笔交易（买入和卖出算一笔交易），目标是最大化利润。

代码思路解析：

1. 问题分析：

• 每天有两种状态：

  1. 持有股票（f[i][j]）：表示第 i 天结束时，完成了 j 笔交易并持有股票的最大利润。

  2. 不持有股票（g[i][j]）：表示第 i 天结束时，完成了 j 笔交易并不持有股票的最大利润。

• 目标是找到最后一天的最大利润。

  

2. 动态规划定义：

• 定义两个状态数组 f 和 g：

  • f[i][j] 表示第 i 天结束时，完成了 j 笔交易并持有股票的最大利润。

  • g[i][j] 表示第 i 天结束时，完成了 j 笔交易并不持有股票的最大利润。

• j 的取值范围是 0 到 k，表示完成的交易笔数。

3. 状态转移方程：

• 持有股票（f[i][j]）：

  • 可能是前一天就持有股票，即 f[i-1][j]。

  • 也可能是今天买入股票，那么前一天必须没有股票，即 g[i-1][j] - prices[i]。

  • 取两者的最大值：

    f[i][j] = max(f[i-1][j], g[i-1][j] - prices[i]);

• 不持有股票（g[i][j]）：

  • 可能是前一天就没有股票，即 g[i-1][j]。

  • 也可能是今天卖出股票，那么前一天必须持有股票，且交易笔数增加 1，即 f[i-1][j-1] + prices[i]。

  • 取两者的最大值：

    g[i][j] = max(g[i-1][j], f[i-1][j-1] + prices[i]);

4. 初始化：

• 第 0 天（初始状态）：

  • f[0][0] = -prices[0]：第 0 天买入股票，利润为 -prices[0]。

  • g[0][0] = 0：第 0 天不持有股票，利润为 0。

  • 其他状态初始化为 -INF（表示不可达状态）。

5. 填表：

• 从 i = 1 开始，逐步计算 f[i][j] 和 g[i][j]，直到 i = n-1。

6. 返回结果：

• 最终的结果是 max(g[n-1][0], g[n-1][1], ..., g[n-1][k])，即最后一天不持有股票的最大利润。

  

优化空间复杂度：

当前的空间复杂度是 O(n * k)，可以通过滚动数组的方式优化到 O(k)：

class Solution {
public:const int INF = 0x3f3f3f3f; // 表示无穷大int maxProfit(int k, vector<int>& prices) {int n = prices.size();if (n == 0) return 0; // 边界条件处理// 处理一个细节问题：最多只能完成 n/2 笔交易k = min(k, n / 2);// 使用滚动数组优化空间复杂度vector<int> f(k + 1, -INF); // 持有股票vector<int> g(k + 1, -INF); // 不持有股票// 初始化f[0] = -prices[0]; // 第 0 天买入股票g[0] = 0;          // 第 0 天不持有股票// 填表for (int i = 1; i < n; i++) {vector<int> new_f(k + 1, -INF);vector<int> new_g(k + 1, -INF);for (int j = 0; j <= k; j++) {new_f[j] = max(f[j], g[j] - prices[i]); // 持有股票new_g[j] = g[j]; // 不持有股票if (j >= 1) // 如果该状态存在new_g[j] = max(new_g[j], f[j - 1] + prices[i]); // 卖出股票}f = new_f;g = new_g;}// 找到最后一行的最大值int ret = 0;for (int j = 0; j <= k; j++)ret = max(ret, g[j]);return ret;}
};

总结：

• 使用动态规划的思想，通过状态转移方程计算每天的最大利润。

• 通过滚动数组优化，空间复杂度从 O(n * k) 降低到 O(k)。

• 最终结果是最后一天不持有股票的最大利润（最多完成 k 笔交易）。