本文主要是介绍Day51 动态规划part10+Day52 动态规划part11,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LC121买卖股票的最佳时机(未掌握)
- 暴力:双层循环寻找最优间距,每一次都确定一个起点,遍历剩余节点当作终点
- 贪心:取最左最小值,不断遍历那么得到的差值最最大值就是最大利润。
- 动态规划
- dp数组的含义:
- dp[i][0] 表示第i天持有股票所得最多现金
- dp[i][1] 表示第i天不持有股票所得最多现金
- 递归式的推导
- dp[i][0]=>第i-1天持有和第i天买入的最多现金=>Math.max(dp[i-1][0],-price[i])
- 因为本金是0,且只能操作一次,所以第i天买入的最多现金为-price[i]
- dp[i][1]=>第i-1天不持有和第i天卖出的最多现金=>Math.max(dp[i-1][1],dp[i-1][0]+price[i])
- dp数组的含义:
- 代码
LC122买卖股票的最佳时机II
- 与LC121买卖股票的最佳时机不同的是,LC121只能买入卖出一次,而LC122可以买入卖出多次,因此第i天买入的最多现金为dp[i-1][1]-price[i]
- 代码
LC123买卖股票的最佳时机III(未掌握)
- LC123与LC122不同的是,LC123只能允许买入两次,而LC122可以买入无数次,因此使用5个状态来记录五种情况
- 0:无操作,这个状态是用来帮助统计第一次持有股票的情况的
- 1:第一次持有股票
- 2:第一次不持有股票
- 3:第二次持有股票
- 4:第二次不持有股票
- 递归公式
- dp[i][0] = dp[i-1][0]
- dp[i][1] => 第i-1天第一次就持有股票和第i-1天不持有股票第i天买入 => Math.max(dp[i-1][1], dp[i-1][0]-price[i])
- dp[i][2] => 第i-1天第一次就不持有股票和第i-1天持有股票第i天卖出 => Math.max(dp[i-1][2], dp[i-1][1]+price[i])
- dp[i][3] => 第i-1天第二次就持有股票和第i-1天第一次不持有股票第i天买入第二次 => Math.max(dp[i-1][3], dp[i-1][2]+price[i])
- dp[i][4] => 第i-1天第二次就不持有股票和第i-1天持有第二次股票第i天卖出 => Math.max(dp[i-1][4], dp[i-1][3]+price[i])
- 初始化:
- 第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;
- 代码
LC188买卖股票的最佳时机IV
- LC123是买入两次,LC188是买入k次,因此j的值应该设置为2k+1种,代表2k+1种情况
- 根据规律可知
- 初始化的时候dp[0][j],只要j为1、3、5…2*k-1时,值为-price[0]
- 同理:j两两一组,表示j次买入股票和卖出股票的最多金额
- 代码
这篇关于Day51 动态规划part10+Day52 动态规划part11的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!