leetcode-股票买卖系列-「动态规划」

发表于 更新于 Artalk： loading...
dp 状态机

前言

《买卖股票的最佳时机》问题合集

121. 买卖股票的最佳时机

问题描述

image-20220322133514205

代码

方案1

本题目限制只能进行一次交易，因此收益最优的策略一定是：在价格最低的时刻 t0t_0 买入，价格最高的时刻 t1t_1 卖出，注意 t0<t1t_0 < t_1 即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    static final int INF = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        int minVal = INF;
        int maxP = -INF;
        for (int i = 0; i < prices.length; ++i) {
            minVal = Math.min(prices[i], minVal);
            maxP = Math.max(maxP, prices[i] - minVal);
        }
        return maxP;
    }
}

通用思路

dpdp 状态机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    static final int INF = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 1][3];
        for (int i = 0; i <= n; ++i) {
            f[i][0] = -INF;
            f[i][1] = -INF;
            f[i][2] = -INF;
        }
        f[0][0] = 0; // 初始条件，第0天，不买不卖收益一定为0
        for (int i = 1; i <= n; ++i) {
            int x = prices[i - 1];
            f[i][0] = f[i - 1][0]; // 第i天 不买不卖的收益
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - x); // 第i天 买入第一支股票的最大收益
            f[i][2] = Math.max(f[i - 1][2], f[i - 1][1] + x); // 第i天 卖出第一支股票的最大收益
        }
        return Math.max(f[n][2],f[n][0]);
    }
}

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

题目描述

image-20220322151802748

代码

方案1

由于可以多次买入卖出，因此找出所有的价格上升区段，将所获的收益加起来即为最大利润

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    
    public int maxProfit(int[] arr) {
       if (arr.length == 1) return 0;

        int ans = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i-1]) {  // 只要卖出有利可图
                ans += (arr[i] - arr[i-1]);
            }
        }

        return ans;
    }
}

通用思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    static final int INF = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 1][2]; // java数组默认初始值为0
        for (int i = 0; i <= n; ++i) {
            f[i][0] = -INF;
            f[i][1] = -INF;
        }
        // 这个初始化很重要
        // 第0天，从意义上说是没有股票可购买并且 手中也不可能有股票，卖出股票收益必须是0
        f[0][1] = 0;
        int x;
        for (int i = 1; i <= n; ++i) {
            x = prices[i - 1];
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] - x); // 第i天 买入股票的最大收益
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] + x); // 第i天 卖出股票的最大收益
        }
        return f[n][1];
    }
}

注意初始化，如果股票价格不为负的话，将每一天的卖出股票的最大收益初始值设置为0即可，就不用特地为第0天初始化了。

  • 再进一步，为什么要将f[i][0]=-INF设置为负最大值？
  • 实际上只需将第0天的初始值f[0][0]买入股票的最大收益设置为-INF即可

第0天没有股票可购买，买入股票的最大收益要设置为一个无意义并且无影响的值。

不影响判断，是指

f[1][0]=max{f[0][0],f[0][1]−x}f[1][0] = max\{f[0][0], f[0][1]-x\}

而实际上 f[1][0]f[1][0] 只能等于 −x-x

1
2
3
4
5
6
7
8
//……
        int[][] f = new int[n + 1][2];
    
        f[0][0] = -INF;
        // 由于创建数组时默认初始化
        // f[0][1] = 0
        int x;
        for (int i = 1; i <= n; ++i) {//……

关于初始值的设定，在问题五中继续拓展思考。

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

如果对交易次数进行限制呢？

问题描述

image-20220322160434452

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    static final int INF = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 1][5];
        // 限定最多买卖两次股票
        f[0][1] = -INF; 
        f[0][3] = -INF;
        for (int i = 1; i <= n; ++i) {
            int x = prices[i - 1];
            f[i][0] = f[i - 1][0]; // 第i天不买不卖的收益
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - x); // 第i天，买入第一支股票的最大收益
            f[i][2] = Math.max(f[i - 1][2], f[i - 1][1] + x); // 第i天，卖出第一支股票的最大收益
            f[i][3] = Math.max(f[i - 1][3], f[i - 1][2] - x); // 第i天，买入第二支股票的最大收益
            f[i][4] = Math.max(f[i - 1][4], f[i - 1][3] + x); // 第i天，卖出第二支股票的最大收益
        }
        return Math.max(f[n][0], Math.max(f[n][2], f[n][4]));
    }
}

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

限定交易次数为 KK

问题描述

image-20220322164305413

代码

dpdp 状态机

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
class Solution {
    static final int INF = 0x3f3f3f3f;
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][][] f = new int[n + 1][k + 1][2];

        for (int j = 0; j <= k; ++j) {
            f[0][j][0] = -INF; // 初始，第0天无法买入任何一支股票
            // 第0天无法执行任何一次交易的买入行为
        }
        
        for (int i = 1; i <= n; ++i) {
            int x = prices[i - 1];
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = Math.max(f[i - 1][j - 1][1] - x, f[i - 1][j][0]);
                f[i][j][1] = Math.max(f[i - 1][j][0] + x, f[i - 1][j][1]);
            }
        }
        int maxP = 0;
        for (int j = 0; j <= k; ++j) {
            maxP = Math.max(f[n][j][1], maxP);
        }
        return maxP;
    }
}

关于初始化，参看以上代码。

从卖出股票合法性方面考虑，进行初始化。

1
2
3
4
5
6
7
8
9
// 先全部初始化为-INF
for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= k; ++j) {
        f[i][j][0] = -INF;
        f[i][j][1] = -INF;
    }
}
// 再初始化每一天，第0次交易卖出股票 收益为0（因为不可能存在这次交易）
for (int i = 0; i < n; ++i) f[i][0][1] = 0;

推荐采用买入合法性的思路进行初始化，

  • 不合法的卖出状态，其收益应该是0，但是java新建数组时，默认初值就是0，无需设置

  • 而且由于后续天数的买入状态 f[i][0]f[i][0] 都会被更新

因此初始化时只需考虑，第0天买入股票的合法性

实际上，第0天无法买入任何股票。因此第0天的买入收益设置一个无意义且无影响的 −INF-INF 即可。

以这种思路回来看第一题，初始条件如何设置呢？

答：f[0][1] = -INF

ps：在第一题中，状态码1代表买入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    static final int INF = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 1][3];
        f[0][1] = -INF;
        // 初始条件，第0天，不买不卖收益一定为0
        // f[0][0] = 0
        for (int i = 1; i <= n; ++i) {
            int x = prices[i - 1];
            f[i][0] = f[i - 1][0]; // 第i天 不买不卖的收益
            f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - x); // 第i天，买入第一支股票的最大收益
            f[i][2] = Math.max(f[i - 1][2], f[i - 1][1] + x); // 第i天，卖出第一支股票的最大收益
        }
        return Math.max(f[n][2],f[n][0]);
    }
}

后话

其实仔细研究发现，这几题的状态转移方程，都只与第 ii 天、第 i−1i-1 天的状态有关，因此可以使用滚动数组进行空间占用上的优化。

以股票买卖的最佳时机IV为例：

唯一需要注意的是，对交易轮次循环时，要从后往前。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    static final int INF = 0x3f3f3f3f;
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] f = new int[k+1][2];
        for (int j = 0; j <= k; ++j) {
            f[j][0] = -INF;
        }
        for (int i = 1; i <= n; ++i) {
            int x = parices[i - 1];
            for (int j = k; j >= 1; --j) {
                f[j][0] = Math.max(f[j - 1][1] - x, f[j][0]);
                f[j][1] = Math.max(f[j][0] + x, f[j][1]);
            }
        }
        int maxP = -INF;
        for (int j = 0; j <= k; ++j) {
            maxP = Math.max(f[j][1], maxP);
        }
        return maxP;
    }
}

最终结果
image-20220322191702394

收工。