LeetCode | 121. 买卖股票的最佳时机

[aermin]

题目

题解

买卖股票类题目的解题模板：

base case： dp[-1][k][0] = dp[i][0][0] = 0 dp[-1][k][1] = dp[i][0][1] = -infinity 状态转移方程： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

动态规划（初始版）

/**
 * 思路：（i是第几天，k是允许交易的最大次数，第三个是当前的持有状态：1表示持有，0表示没有持有）
 * 今天我没有持有股票，有两种可能：
 * 要么是我昨天就没有持有，然后今天选择不操作，所以我今天还是没有持有；
 * 要么是我昨天持有股票，但是今天我卖出去了，所以我今天没有持有股票了。
 * 状态转移方程1：dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
 * 今天我持有股票，有两种可能：
 * 要么是我昨天就持有，然后今天选择不操作，所以我今天还是持有；
 * 要么是我昨天没持有股票，但是今天我买了，所以我今天持有股票了。
 * 状态转移方程2：dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
 *
 * 关于k：
 * k表示的是第i天至多交易k次；
 * k-1 是对于 i-1 的，这个上一波循环已经算出来了；
 * k 是一个最大次数限制，随着交易进行，可以进行的最大交易次数在减少；
 * 本题最多只允许完成一笔交易, 所以k都为1，可都去掉k。
 * 完成一次交易（即买入和卖出一支股票一次，两个操作）,
 * 所以动态方程1和方程2共卖出和买入两次操作，为一笔交易，k-1写一次即可，
 * 即上面两个方程也可写成：
 * dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k-1][1] + prices[i])
 * dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
 */

/*
 * @lc app=leetcode.cn id=121 lang=javascript
 *
 * [121] 买卖股票的最佳时机
 */

// @lc code=start
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let n = prices.length;
    if(n === 0) return 0;
    const dp = new Array(n).fill([]);
    for(let i = 0; i < n; i ++) {
        // i = 0的时候 i-1 = -1,dp[-1]的情况不存在，需要处理
        if(i=== 0) {
            // dp[i][0] = max(dp[-1][0], dp[-1][1] + prices[i]); = max(0, -infinity)
            // dp[-1][0]为0，dp[-1][1]因为不存在的那天不可能持有，所以为-infinity表示不存在
            dp[i][0] = 0;
            // dp[i][1] = max(dp[i-1][1], - prices[i]); = max(-infinity, - prices[i])
            dp[i][1] = - prices[i];
            continue;
        }

        // dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
        //dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])

        // dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
        // dp[i-1][0][0]: 因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0
        // dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
        //             = max(dp[i-1][1][1], - prices[i])

        // 发现k都为1，所以都去掉k
        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[n-1][0];
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，只需要遍历一次。 空间复杂度：O(n)，用dp数组存储。

动态规划（优化版）

/**
 * 思路：优化上面解法，新状态只和相邻的一个状态有关，所以不用整个 dp 数组，
 * 只需要一个变量储存相邻的那个状态就足够了，这样可以把空间复杂度降到 O(1):
*/
var maxProfit = function(prices) {
    let dp_i_0 = 0, dp_i_1 = -Infinity;
    for(let i = 0; i < prices.length; i ++) {
        //dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        //dp[i][1] = Math.max(dp[i-1][1], - prices[i]);
        dp_i_1 = Math.max(dp_i_1, -prices[i])
    }
    return dp_i_0;
}

复杂度分析

时间复杂度：O(n)，只需要遍历一次。 空间复杂度：O(1)，只使用了常数个变量。

Reference

一个方法团灭 6 道股票问题 作者：labuladong

[crossgo-web]