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

简介: 前言本篇文章我们来学习下动态规划中的两个经典题型,打家劫舍和股票买卖,通过两个题型来巩固动态规划解题思路。

「这是我参与2022首次更文挑战的第5天,活动详情查看:2022首次更文挑战


前言


本篇文章我们来学习下动态规划中的两个经典题型,打家劫舍和股票买卖,通过两个题型来巩固动态规划解题思路。


打家劫舍57.png

打家劫舍其实比较简单


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

58.png

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



相关文章
【动态规划】198. 打家劫舍
【动态规划】198. 打家劫舍
|
7月前
力扣198.打家劫舍(简单动态规划)
力扣198.打家劫舍(简单动态规划)
|
6月前
|
Java Go C++
Leetcode70. 爬楼梯(动态规划)
Leetcode70. 爬楼梯(动态规划)
32 0
|
7月前
力扣213打家劫舍2(简单动态规划)
力扣213打家劫舍2(简单动态规划)
|
算法
【学会动态规划】打家劫舍 II(12)
【学会动态规划】打家劫舍 II(12)
28 0
|
存储 Cloud Native Go
198. 打家劫舍:动态规划
这是 力扣上的 198. 打家劫舍,难度为 中等。
|
Go Cloud Native
213. 打家劫舍 II:动态规划
这是 力扣上的 213. 打家劫舍 II,难度为 中等。
100 1
|
机器学习/深度学习 Cloud Native Go
337.打家劫舍 III:动态规划
这是力扣上的 337. 打家劫舍 III,难度为 中等。
|
算法 Java Python
【LeetCode】 53. 最大子序和(动态规划)
53. 最大子序和(动态规划)
98 0
【LeetCode】 53. 最大子序和(动态规划)
|
算法 Java 测试技术
【LeetCode】 53. 最大子序和(贪心算法)
53. 最大子序和(贪心算法)
95 0