目录
一、面试题 17.16. 按摩师 - 力扣（LeetCode）
四、 LCR 091. 粉刷房子 - 力扣（LeetCode）
五、309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）
六、 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）
七、123. 买卖股票的最佳时机 III - 力扣（LeetCode）
八、 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
一、面试题 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，表示每个预约的时长或价值，要求在不连续选择相邻元素的情况下，找到最大价值的组合。
代码思路解析：
问题分析：
每个元素
nums[i]表示第i个预约的价值。不能选择相邻的预约，即如果选择了
nums[i]，就不能选择nums[i-1]和nums[i+1]。目标是找到一种选择方式，使得总价值最大。
动态规划定义：
定义两个状态数组
f和g：f[i]表示选择第i个预约时的最大价值。g[i]表示不选择第i个预约时的最大价值。
通过这两个状态数组，可以递推地计算出每一步的最优解。
状态转移方程：
如果选择第
i个预约，那么前一个预约不能选择，因此f[i] = g[i-1] + nums[i]。如果不选择第
i个预约，那么前一个预约可以选择或不选择，取两者中的最大值，因此g[i] = max(f[i-1], g[i-1])。
初始化：
f[0] = nums[0]：如果只有一个预约，那么选择它的价值就是nums[0]。g[0] = 0：如果不选择第一个预约，那么价值为 0。
填表：
从
i = 1开始，逐步计算f[i]和g[i]，直到i = n-1。
返回值：
最终的结果是
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. 主函数 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++) {
// 选择颜色 0
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
// 选择颜色 1
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
// 选择颜色 2
dp[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]; // 选择颜色 0
int new_dp1 = min(dp0, dp2) + costs[i - 1][1]; // 选择颜色 1
int new_dp2 = min(dp0, dp1) + costs[i - 1][2]; // 选择颜色 2
dp0 = 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]; // 选择颜色 0
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]; // 选择颜色 1
dp[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. 问题分析：
每天有三种状态：
持有股票（
dp[i][0]）：表示第i天结束时持有股票的最大利润。不持有股票且处于冷冻期（
dp[i][1]）：表示第i天结束时没有股票，且处于冷冻期的最大利润。不持有股票且不处于冷冻期（
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. 问题分析：
每天有两种状态：
持有股票（
f[i]）：表示第i天结束时持有股票的最大利润。不持有股票（
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. 问题分析：
每天有两种状态：
持有股票（
f[i][j]）：表示第i天结束时，完成了j笔交易并持有股票的最大利润。不持有股票（
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. 问题分析：
每天有两种状态：
持有股票（
f[i][j]）：表示第i天结束时，完成了j笔交易并持有股票的最大利润。不持有股票（
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笔交易）。