「这是我参与2022首次更文挑战的第5天，活动详情查看：2022首次更文挑战」
前言
本篇文章我们来学习下动态规划中的两个经典题型，打家劫舍和股票买卖，通过两个题型来巩固动态规划解题思路。
打家劫舍
打家劫舍其实比较简单
1. 定义DP数组及下标含义
我们要求的是偷窃n间房子的最大价值，求谁设谁，我们定义DP数组，将dp[i]记录为偷窃[1,i]房子的最大价值
当然，作为职业小偷，为了不出发警报，我们只是偷取[0, i]中的某几间房子
const dp = [] // dp[i] 表示偷窃[0,第i间房子]的最大价值 复制代码
2. 递推公式
如果不考虑是否触发警报，那么偷取[0, i]间房子的最大价值肯定是将它们累加即可。但是在考虑警报的情况下，那么对于第i间房子，我们有两种选择
- 偷取第i间房子的东西，此时就不能盗窃第i-1的房子
要注意第i间房子对应的价值为nums[i - 1]
dp[i] = nums[i - 1] + dp[i - 2] 复制代码
- 不偷取第i间房子的东西，此时最大价值就等于偷取[0, i - 1]的最大价值
dp[i] = dp[i - 1] 复制代码
我们综合下两种情况可以得到递推公式
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]) 复制代码
3. DP初始化
我们刚刚定义的dp[i]为偷取第i间房子的最大价值，所以相应的dp[0]表示可偷取的房子为0，而dp[1]等于nums[0]
dp[0] = 0 dp[1] = nums[0] 复制代码
4. dp遍历生成
这步就很简单了，一次循环即可完成
for (let i = 2; i <= m; i++) { // ... } 复制代码
5. 完整代码
var rob = function(nums) { const dp = [] const m = nums.length dp[0] = 0 dp[1] = nums[0] for (let i = 2; i <= m; i++) { dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]) } return dp[m] }; 复制代码
买卖股票的最佳时机
1. 定义DP数组及下标
我们要求的是N天股票买卖最大获利，求谁设谁，我们将dp定义为前i天股票买卖的最大获利，dp[i]表示买卖股票在[0,i]天时的最大获利
const dp = [] // dp[i]表示在[0,第i天]买卖的最大获利 复制代码
2. 递归公式
我们再思考下，什么情况下我们希望吃后悔药，推迟卖出，当然是明天价格比今天高的时候。
什么时候我们会想着立即卖出，或者不买，那应该就是明天价格比今天低的时候。
所以本题的关键在于捕捉到这种价格变化下的理想操作变化。当价格即将下跌之前卖出，在价格上涨前买入。此时我们获利为这种价格的高低差。
- 当股票价格大于前一天时候，当天应该是卖出的一个时机（当然不代表我们一定会在当天卖出，还得看后面的价格波动），我们的最大获利为上一天为止的最大获利加上
- 当天与上天的价差
注意第i天的股票价值为i-1
dp[i] = dp[i - 1] + prices[i - 1] - prices[i - 2] 复制代码
- 当股票价格小于前一天的时候，当天应该是买进的一个时机（不代表我们会在当天买进），我们最大获利和上一天的最大获利相等
dp[i] = dp[i - 1] 复制代码
所以综合两种情况，我们的最大获利递推公式为
if (prices[i - 1] > prices[i - 2]) { dp[i] = dp[i - 1] + (prices[i - 1] - prices[i - 2]) } else { dp[i] = dp[i - 1] } 复制代码
3. dp初始化
在第0天和第1天我们都是无法获利的，所以
dp[0] = 0 dp[1] = 0 复制代码
4. dp数组遍历生成
比较简单，我们从第2天开始，一次循环可以完成
for (let i = 2; i <= m; i++) { // ... } 复制代码
5. 完整代码
var maxProfit = function(prices) { const dp = [] const m = prices.length dp[0] = 0 dp[1] = 0 for (let i = 2; i <= m; i++) { if (prices[i - 1] > prices[i - 2]) { dp[i] = dp[i - 1] + (prices[i - 1] - prices[i - 2]) } else { dp[i] = dp[i - 1] } } return dp[m] } 复制代码
结语
本篇文章讲解了leetcode上两个比较经典的系列：打家劫舍和买卖股票，选取了比较有代表性的一题来分析解答过程，通过两道真题让我们巩固动态规划的解题思路。
至此，我将目前学习到的比较经典的动态规划基本已经记录完毕。动态规划实际的难点在于dp数组的定义和递推公式的推导，这也许是通过几道题无法熟练掌握的，可能需要不断低反复练习才能更加理解和掌握。
