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

动态规划Day5学习心得

web 2025/7/31 8:18:15

今天继续看动态规划的题目。

首先是昨天的打家劫舍的最后一道变题：337. 打家劫舍 III - 力扣（LeetCode）

这道题目实际上是一个关于二叉树的遍历过程加上动态规划的dp数组。

对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。

本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。

暴力递归

代码如下：

class Solution {
public:int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left，相当于不考虑左孩子了if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right，相当于不考虑右孩子了// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子return max(val1, val2);}
};

当然以上代码超时了，这个递归的过程中其实是有重复计算了。

计算root的四个孙子（左右孩子的孩子）为头结点的子树的情况，又计算了root的左右孩子为头结点的子树的情况，计算左右孩子的时候其实又把孙子计算了一遍。

记忆化递推

所以可以使用一个map把计算过的结果保存一下，这样如果计算过孙子了，那么计算孩子的时候可以复用孙子节点的结果。

代码如下：

class Solution {
public:unordered_map<TreeNode* , int> umap; // 记录计算过的结果int rob(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return root->val;if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回// 偷父节点int val1 = root->val;if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->leftif (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right// 不偷父节点int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子umap[root] = max(val1, val2); // umap记录一下结果return max(val1, val2);}
};

动态规划

在上面两种方法，其实对一个节点偷与不偷得到的最大金钱都没有做记录，而是需要实时计算。

而动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。

确定递归函数的参数和返回值

这里我们要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

参数为当前节点，代码如下：

vector<int> robTree(TreeNode* cur) {

其实这里的返回数组就是dp数组。

所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

所以本题dp数组就是一个长度为2的数组！

那么有同学可能疑惑，长度为2的数组怎么标记树中每个节点的状态呢？

别忘了在递归的过程中，系统栈会保存每一层递归的参数。

如果还不理解的话，就接着往下看，看到代码就理解了哈。

确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

if (cur == NULL) return vector<int>{0, 0};

这也相当于dp数组的初始化

确定遍历顺序

首先明确的是使用后序遍历。因为要通过递归函数的返回值来做下一步计算。

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

代码如下：

// 下标0：不偷，下标1：偷
vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右
// 中

确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

代码如下：

vector<int> left = robTree(cur->left); // 左
vector<int> right = robTree(cur->right); // 右// 偷cur
int val1 = cur->val + left[0] + right[0];
// 不偷cur
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};

class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}// 长度为2的数组，0：不偷，1：偷vector<int> robTree(TreeNode* cur) {if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);// 偷cur，那么就不能偷左右节点。int val1 = cur->val + left[0] + right[0];// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};

然后看第二题：121. 买卖股票的最佳时机 - 力扣（LeetCode）

贪心

因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

C++代码如下：

class Solution {
public:int maxProfit(vector<int>& prices) {int low = INT_MAX;int result = 0;for (int i = 0; i < prices.size(); i++) {low = min(low, prices[i]);  // 取最左最小价格result = max(result, prices[i] - low); // 直接取最大区间利润}return result;}
};

动态规划

动规五部曲分析如下：

确定dp数组（dp table）以及下标的含义

dp[i][0] 表示第i天持有股票所得最多现金，一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]，这是一个负数。dp[i][1] 表示第i天不持有股票所得最多现金

注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态

确定递推公式

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]，也可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

这样递推公式就分析完了

dp数组如何初始化

由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出

其基础都是要从dp[0][0]和dp[0][1]推导出来。

那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;

确定遍历顺序

从递推公式可以看出dp[i]都是由dp[i - 1]推导出来的，那么一定是从前向后遍历。

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};

然后看买股票的变题：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

本题和上一题的唯一区别是本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）

在动规五部曲中，这个区别主要是体现在递推公式上，其他都和上一题一样一样的。

所以重点讲一讲递推公式。

这里重申一下dp数组的含义：

dp[i][0] 表示第i天持有股票所得现金。
dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]

注意这里和上一题唯一不同的地方，就是推导dp[i][0]的时候，第i天买入股票的情况。

在上一题中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]。

而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。

那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]。

再来看看如果第i天不持有股票即dp[i][1]的情况，依然可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

注意这里和上一题就是一样的逻辑，卖出股票收获利润（可能是负值）天经地义！

代码如下：（注意代码中的注释，标记了和121.买卖股票的最佳时机唯一不同的地方）

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[len - 1][1];}
};

然后继续看变题：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

接来下用动态规划五部曲详细分析一下：

确定dp数组以及下标的含义

一天一共就有五个状态，

没有操作（其实也可以不设置这个状态）
第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票。

例如 dp[i][1] ，并不是说第i天一定买入股票，有可能第 i-1天就买入了，那么 dp[i][1] 延续买入股票的这个状态。

确定递推公式

达到dp[i][1]状态，有两个具体操作：

操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？

一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分：

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

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

dp数组如何初始化

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，这个初始值应该是多少呢？

此时还没有买入，怎么就卖出呢？其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;

第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？

第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。

所以第二次买入操作，初始化为：dp[0][3] = -prices[0];

同理第二次卖出初始化dp[0][4] = 0;

确定遍历顺序

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0];dp[0][3] = -prices[0];for (int i = 1; i < prices.size(); i++) {dp[i][0] = dp[i - 1][0];dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}return dp[prices.size() - 1][4];}
};

然后再看一道变题：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

相当于再上题的基础上，买卖次数由原来的两次变成了k次。

动规五部曲，分析如下：

确定dp数组以及下标的含义

本题其实依然可以用一个二维dp数组。

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]

j的状态表示为：

0 表示不操作
1 第一次买入
2 第一次卖出
3 第二次买入
4 第二次卖出
.....

除了0以外，偶数就是卖出，奇数就是买入。

题目要求是至多有K笔交易，那么j的范围就定义为 2 * k + 1 就可以了。

所以二维dp数组的C++定义为：

vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));

确定递推公式

还要强调一下：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票。

达到dp[i][1]状态，有两个具体操作：

操作一：第i天买入股票了，那么dp[i][1] = dp[i - 1][0] - prices[i]
操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可以类比剩下的状态，代码如下：

for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

dp数组如何初始化

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，这个初始值应该是多少呢？

此时还没有买入，怎么就卖出呢？其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;

第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？

第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后在买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。

所以第二次买入操作，初始化为：dp[0][3] = -prices[0];

第二次卖出初始化dp[0][4] = 0;

所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]

代码如下：

for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];
}

在初始化的地方同样要类比j为偶数是卖、奇数是买的状态。

确定遍历顺序

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

C++代码如下：

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];}for (int i = 1;i < prices.size(); i++) {for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

然后是最后一道变题：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

相对于第二个买股票的题目，本题加上了一个冷冻期。

动规五部曲，分析如下：

确定dp数组以及下标的含义

dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。

出现冷冻期之后，状态其实是比较复杂度，例如今天买入股票、今天卖出股票、今天是冷冻期，都是不能操作股票的。

具体可以区分出如下四个状态：

状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
- 状态三：今天卖出股票
状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

j的状态为：

0：状态一
1：状态二
2：状态三
3：状态四

本题为什么要单独列出「今天卖出股票」一个状态呢？

因为本题我们有冷冻期，而冷冻期的前一天，只能是「今天卖出股票」状态，如果是「不持有股票状态」那么就很模糊，因为不一定是卖出股票的操作。

注意这里的每一个状态，例如状态一，是持有股票股票状态并不是说今天一定就买入股票，而是说保持买入股票的状态即：可能是前几天买入的，之后一直没操作，所以保持买入股票的状态。

确定递推公式

达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：

操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
操作二：今天买入了，有两种情况
- 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
- 前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]

那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

操作一：前一天就是状态二
操作二：前一天是冷冻期（状态四）

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

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

昨天一定是持有股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

综上分析，递推代码如下：

dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];

dp数组如何初始化

这里主要讨论一下第0天如何初始化。

如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，一定是当天买入股票。

保持卖出股票状态（状态二），这里其实从「状态二」的定义来说，很难明确应该初始多少，这种情况我们就看递推公式需要我们给他初始成什么数值。

如果i为1，第1天买入股票，那么递归公式中需要计算 dp[i - 1][1] - prices[i] ，即 dp[0][1] - prices[1]，那么大家感受一下 dp[0][1] （即第0天的状态二）应该初始成多少，只能初始为0。想一想如果初始为其他数值，是我们第1天买入股票后手里还剩的现金数量是不是就不对了。

今天卖出了股票（状态三），同上分析，dp[0][2]初始化为0，dp[0][3]也初始为0。

确定遍历顺序

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0;vector<vector<int>> dp(n, vector<int>(4, 0));dp[0][0] -= prices[0]; // 持股票for (int i = 1; i < n; i++) {dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] = dp[i - 1][0] + prices[i];dp[i][3] = dp[i - 1][2];}return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));}
};

查看全文

http://www.xdnf.cn/news/16756.html