代码随想录算法训练营day41｜动态规划part08

第一题：121. Best Time to Buy and Sell Stock
   贪心法：

1. class Solution {
2.     public int maxProfit(int[] prices) {
3.         // 找到一个最小的购入点
4.         int low = Integer.MAX_VALUE;
5.         // res不断更新，直到数组循环完毕
6.         int res = 0;
7.         for(int i = 0; i < prices.length; i++){
8.             low = Math.min(prices[i], low);
9.             res = Math.max(prices[i] - low, res);
10.         }
11.         return res;
12.     }
13. }

复制代码

  动态规划：版本一

1. // 解法1
2. class Solution {
3.     public int maxProfit(int[] prices) {
4.         if (prices == null || prices.length == 0) return 0;
5.         int length = prices.length;
6.         // dp[i][0]代表第i天持有股票的最大收益
7.         // dp[i][1]代表第i天不持有股票的最大收益
8.         int[][] dp = new int[length][2];
9.         int result = 0;
10.         dp[0][0] = -prices[0];
11.         dp[0][1] = 0;
12.         for (int i = 1; i < length; i++) {
13.             dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
14.             dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
15.         }
16.         return dp[length - 1][1];
17.     }
18. }

复制代码

  动态规划：版本二(利用二維數組（和卡哥思路同等），下面還有利用一維滾動數組的更優化版本)

1. class Solution {
2.     public int maxProfit(int[] prices) {
3.         int len = prices.length;
4.         int dp[][] = new int[2][2];
5.         
6.         dp[0][0] = - prices[0];
7.         dp[0][1] = 0;
9.         for (int i = 1; i < len; i++){
10.             dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], - prices[i]);
11.             dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
12.         }
13.         return dp[(len - 1) % 2][1];
14.     }
15. }

复制代码

  动态规划：版本二(利用一維數組)

1. class Solution {
2.   public int maxProfit(int[] prices) {
3.     int[] dp = new int[2];
4.     // 记录一次交易，一次交易有买入卖出两种状态
5.     // 0代表持有，1代表卖出
6.     dp[0] = -prices[0];
7.     dp[1] = 0;
8.     // 可以参考斐波那契问题的优化方式
9.     // 我们从 i=1 开始遍历数组，一共有 prices.length 天，
10.     // 所以是 i<=prices.length
11.     for (int i = 1; i <= prices.length; i++) {
12.       // 前一天持有；或当天买入
13.       dp[0] = Math.max(dp[0], -prices[i - 1]);
14.       // 如果 dp[0] 被更新，那么 dp[1] 肯定会被更新为正数的 dp[1]
15.       // 而不是 dp[0]+prices[i-1]==0 的0，
16.       // 所以这里使用会改变的dp[0]也是可以的
17.       // 当然 dp[1] 初始值为 0 ，被更新成 0 也没影响
18.       // 前一天卖出；或当天卖出, 当天要卖出，得前一天持有才行
19.       dp[1] = Math.max(dp[1], dp[0] + prices[i - 1]);
20.     }
21.     return dp[1];
22.   }
23. }

复制代码

第二题：122. Best Time to Buy and Sell Stock II

1. // 动态规划
2. class Solution
3.     // 实现1：二维数组存储
4.     // 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储
5.     // 时间复杂度：O(n)，空间复杂度：O(n)
6.     public int maxProfit(int[] prices) {
7.         int n = prices.length;
8.         int[][] dp = new int[n][2];     // 创建二维数组存储状态
9.         dp[0][0] = 0;                   // 初始状态
10.         dp[0][1] = -prices[0];
11.         for (int i = 1; i < n; ++i) {
12.             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);    // 第 i 天，没有股票
13.             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第 i 天，持有股票
14.         }
15.         return dp[n - 1][0];    // 卖出股票收益高于持有股票收益，因此取[0]
16.     }
17. }

复制代码

1. //DP using 2*2 Array (下方還有使用一維滾動數組的更優化版本)
2. class Solution {
3.     public int maxProfit(int[] prices) {
4.         int dp[][] = new int [2][2];
5.         //dp[i][0]: holding the stock
6.         //dp[i][1]: not holding the stock
7.         dp[0][0] = - prices[0];
8.         dp[0][1] = 0;
10.         for(int i = 1; i < prices.length; i++){
11.             dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
12.             dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
13.         }
14.         return dp[(prices.length - 1) % 2][1];
15.     }
16. }

复制代码

1. // 优化空间
2. class Solution {
3.     public int maxProfit(int[] prices) {
4.         int[] dp = new int[2];
5.         // 0表示持有，1表示卖出
6.         dp[0] = -prices[0];
7.         dp[1] = 0;
8.         for(int i = 1; i <= prices.length; i++){
9.             // 前一天持有; 既然不限制交易次数，那么再次买股票时，要加上之前的收益
10.             dp[0] = Math.max(dp[0], dp[1] - prices[i-1]);
11.             // 前一天卖出; 或当天卖出，当天卖出，得先持有
12.             dp[1] = Math.max(dp[1], dp[0] + prices[i-1]);
13.         }
14.         return dp[1];
15.     }
16. }

复制代码

 
第三题：123. Best Time to Buy and Sell Stock III 

1. // 版本一
2. class Solution {
3.     public int maxProfit(int[] prices) {
4.         int len = prices.length;
5.         // 边界判断, 题目中 length >= 1, 所以可省去
6.         if (prices.length == 0) return 0;
8.         /*
9.          * 定义 5 种状态:
10.          * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
11.          */
12.         int[][] dp = new int[len][5];
13.         dp[0][1] = -prices[0];
14.         // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
15.         dp[0][3] = -prices[0];
17.         for (int i = 1; i < len; i++) {
18.             dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
19.             dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
20.             dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
21.             dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
22.         }
24.         return dp[len - 1][4];
25.     }
26. }
28. // 版本二: 空间优化
29. class Solution {
30.     public int maxProfit(int[] prices) {
31.         int[] dp = new int[4];
32.         // 存储两次交易的状态就行了
33.         // dp[0]代表第一次交易的买入
34.         dp[0] = -prices[0];
35.         // dp[1]代表第一次交易的卖出
36.         dp[1] = 0;
37.         // dp[2]代表第二次交易的买入
38.         dp[2] = -prices[0];
39.         // dp[3]代表第二次交易的卖出
40.         dp[3] = 0;
41.         for(int i = 1; i <= prices.length; i++){
42.             // 要么保持不变，要么没有就买，有了就卖
43.             dp[0] = Math.max(dp[0], -prices[i-1]);
44.             dp[1] = Math.max(dp[1], dp[0]+prices[i-1]);
45.             // 这已经是第二次交易了，所以得加上前一次交易卖出去的收获
46.             dp[2] = Math.max(dp[2], dp[1]-prices[i-1]);
47.             dp[3] = Math.max(dp[3], dp[2]+ prices[i-1]);
48.         }
49.         return dp[3];
50.     }
51. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。