代码随想录第41天 | 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV

123.买卖股票的最佳时机III

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    const len = prices.length
    const dp = new Array(len).fill(0).map(x => new Array(5).fill(0));
    // 第一天买入（第一次买入）
    dp[0][1] = -prices[0];
    // 第一天买入（第二次买入）（因为他规定，最多买两次，也就是可以只买一次，相当于没有买第一次）
    dp[0][3] = -prices[0];
    for (let i = 1; i < len; i++) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }
    return dp[len - 1][4];

    // const len = prices.length;
    // const dp = new Array(5).fill(0);
    // dp[1] = -prices[0];
    // dp[3] = -prices[0];
    // for (let i = 1; i < len; i++) {
    //     dp[1] = Math.max(dp[1], dp[0] - prices[i]);
    //     dp[2] = Math.max(dp[2], dp[1] + prices[i]);
    //     dp[3] = Math.max(dp[3], dp[2] - prices[i]);
    //     dp[4] = Math.max(dp[4], dp[3] + prices[i]);
    // }
    // return dp[4];
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

思路

188.买卖股票的最佳时机IV

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */

var maxProfit = function (k, prices) {
    const len = prices.length;
    const dp = new Array(k * 2 + 1).fill(0);
    for (let i = 0; i < k; i++) {
        dp[2 * i + 1] = -prices[0]
    }
    for (let i = 1; i < len; i++) {
        for (let j = 1; j < k * 2 + 1; j++)
            if (j % 2 == 1)
                dp[j] = Math.max(dp[j], dp[j - 1] - prices[i]);
            else
                dp[j] = Math.max(dp[j], dp[j - 1] + prices[i]);
    }
    return dp[2 * k ];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思想

延用上一题