动态规划-打家劫舍和股票买卖

「这是我参与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]
};
复制代码

买卖股票的最佳时机

leetcode-122

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数组的定义和递推公式的推导，这也许是通过几道题无法熟练掌握的，可能需要不断低反复练习才能更加理解和掌握。