[LeetCode] 买卖股票的最佳时机 #167

plh97 · 2020-10-05T17:35:13Z

穷举框架

上面这个问题可以通过穷举框架罗列出所有可能. 递归是一种思路啦, 但是下面通过for循环+状态机, 同样可以达到穷举的效果.

框架

for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

显而易见, 状态1 代表哪一天操作股票, 状态2代表还剩下几次交易可以做, 状态3代表: [买, 卖, 啥也不做] 三种状态.

而对于这个题目, 我们想要的是 dp[n-1][K][1] 的结果.

同样有这样的公式

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
- 解释: 我今天没有股票
  - 可能1: 昨天也没持有
  - 可能2: 昨天卖了股票
  - 取最大值
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
- 解释: 我今天持有股票
  - 可能1: 昨天就持有
  - 可能2: 昨天买了股票
  - 取最大值

通过这两个公式, 层层向上叠加, 进而得到 dp[n-1][K][1],

ok 最关键的一步已经完成, 接下来就秒杀这几个问题吧.

买卖股票的最佳时机

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let sz = prices.length
    if (sz==0) return 0
    let dp = Array(sz).fill([])
    // console.log(dp)
    // 0 unhave
    // 1 have
    for(let i=0;i<sz;i++) {
        if (i==0) {
            dp[0][0] = 0
            dp[0][1] = -prices[0]
        }else{
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp[i][1] = Math.max(dp[i-1][1], -prices[i])
        }
    }
    return dp[sz-1][0]
};