Table of Contents

一、股票交易问题

121. 买卖股票的最佳时机

首先对于这道题目，第一想法时直接遍历，计算第 i 天卖出的最大价格，与全局最大利润比较。用两个变量保存即可，一个保存最大利润、另一个保存第 i 天之前最小的买入价格。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int max = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return max;
    }
}

还可以用单调栈、最大子序和

122. 买卖股票的最佳时机 II

仔细思考就会发现递增的价格差累加即可。贪心的一种

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int maxProfit(int[] prices) {
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1])
                sum += prices[i] - prices[i-1];
        }
        return sum;
    }
}

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

使用动态规划，定义状态如下：

1
2
3
4
5
6
7
8
9

dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

1
2
3
4
5
6
7

base case：
dp[-1][...][0] = dp[...][0][0] = 0
dp[-1][...][1] = dp[...][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])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maxProfit(int[] prices) {
        int m = prices.length;
        int[][][] dp = new int[m+1][2][2];
        dp[0][1][1] = -Integer.MAX_VALUE;
        dp[0][1][0] = 0;
        dp[0][0][1] = -Integer.MAX_VALUE;
        dp[0][0][0] = 0;
        for (int i = 1; i <= m; i++) {
            dp[i][1][1] = Math.max(-prices[i-1], dp[i-1][1][1]);
            dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][1][1] + prices[i-1]);
            dp[i][0][1] = Math.max(dp[i-1][0][1], dp[i-1][1][0] - prices[i-1]);
            dp[i][0][0] = Math.max(dp[i-1][0][0], dp[i-1][0][1] + prices[i-1]);
        }
        return dp[m][0][0];
    }
}

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

对于任意的k值有如下代码：

 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

int maxProfit_k_any(int max_k, int[] prices) {
    int n = prices.length;
    if (n <= 0) {
        return 0;
    }
    if (max_k > n / 2) {
        // 交易次数 k 没有限制的情况
        return maxProfit_k_inf(prices);
    }

    // base case：
    // dp[-1][...][0] = dp[...][0][0] = 0
    // dp[-1][...][1] = dp[...][0][1] = -infinity
    int[][][] dp = new int[n][max_k + 1][2];
    // k = 0 时的 base case
    for (int i = 0; i < n; i++) {
        dp[i][0][1] = Integer.MIN_VALUE;
        dp[i][0][0] = 0;
    }

    for (int i = 0; i < n; i++) 
        for (int k = max_k; k >= 1; k--) {
            if (i - 1 == -1) {
                // 处理 i = -1 时的 base case
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i];
                continue;
            }
            dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
            dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);     
        }
    return dp[n - 1][max_k][0];
}