当前位置：首页 > news >正文

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

news 来源：原创 2025/8/29 3:43:34

一、面试题 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，表示每个预约的时长或价值，要求在不连续选择相邻元素的情况下，找到最大价值的组合。

代码思路解析：

问题分析：
- 每个元素 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++) {// 选择颜色 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 笔交易）。

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

目录一、面试题 17.16. 按摩师 - 力扣（LeetCode） 算法代码： 代码思路解析： 问题分析： 动态规划定义： 状态转移方程： 初始化： 填表： 返回值： 优化空…...

编程日记 2025/8/29 3:43:34

【电路笔记 TMS320C6***DSP】外部存储器接口 A EMIFA向FPGA(作为异步存储器)写入数据的示例

目录 DSP和FPGA的连接DSP端：传输数据给FPGAFPGA端：接收数据 EMIFA（External Memory Interface A）的“异步存储器”（Asynchronous Memory）指的是那些不与系统时钟同步进行读写操作的外部存储设备。这类存储器…...

编程日记 2025/8/29 3:41:01

pgsql 查看数据库、表、索引大小等

查询数据库大小 -- 查询单个数据库大小 select pg_size_pretty(pg_database_size(postgres)) as size;-- 查询所有数据库大小 select datname, pg_size_pretty (pg_database_size(datname)) AS size from pg_database; 查询表大小 -- 查询单个表大小 select pg_size_pretty(p…...

编程日记 2025/8/22 15:22:27

物联网感知层采集的数据经过etl 后，输送给ai 训练模型和模型本身调优

在物联网（IoT）系统中，感知层采集的数据经过 ETL（Extract, Transform, Load）处理后，可以作为 AI 模型的训练数据，用于模型训练和调优。以下是实现这一过程的详细步骤和技术方案：一、数据流程概述数据采集：通过传感器和物联网设备采集原始数据。ETL 处理：对原始数据…...

编程日记 2025/8/28 1:48:13

C语言基础

一、基础 C语言文件后缀 .c为源文件 .h为头文件以 Visual studio 为例右键点击源文件点击添加，新建项 .c为C语言文件，.cpp为C文件后缀不同编译器会按照不同的编译语法进行编译 .cpp以C语法第一个程序 #include <stdio.h> //包含 st…...

编程日记 2025/8/28 8:50:01

pinginfoview网络诊断工具中文版

介绍 pinginfoview中文版本是一款实用的网络诊断工具，它专为中文用户设计，提供了方便易用的界面，使得在Windows环境下进行ping测试变得更加简单。该工具是由NirSoft开发的一款免费的桌面应用程序，尽管官方可能并未正式发布中文版…...

编程日记 2025/8/26 18:18:59

Anyting LLM LLM温度设置范围

在Anything LLM中，LLM（Language Model）的温度设置是一个关键参数，它影响着模型生成文本时的随机性和确定性。关于Anything LLM的LLM温度设置范围，虽然没有官方的明确数值范围说明，但通常温度参数的设置遵循…...

编程日记 2025/8/29 3:42:54

鸿蒙Android4个脚有脚线

效果 min:number122max:number150Row(){Stack(){// 底Text().border({width:2,color:$r(app.color.yellow)}).height(this.max).aspectRatio(1)// 长Text().backgroundColor($r(app.color.white)).height(this.max).width(this.min)// 宽Text().backgroundColor($r(app.color.w…...

编程日记 2025/8/28 13:48:54