309. Best Time to Buy and Sell Stock with Cooldown(Medium)

题目描述
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路
确定状态：持有、不持有且在冷冻期、不持有且不在冷冻期
确定状态转移方程：
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
dp[i][1] = dp[i-1][0]+prices[i];
dp[i][2] = Math.max(dp[i-1][1],dp[i-1][2]);

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

内存优化

思路
每次仅用到上一次的数据。

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

结果
image.png

714. Best Time to Buy and Sell Stock with Transaction Fee (Medium)

题目描述
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
思路
确定状态：持有、不持有。
确定状态转移：dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
dp[i][1] = Math.max(dp[i-1][0]+prices[i]-fee, dp[i-1][1]);

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

内存优化

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

结果
image.png

123. Best Time to Buy and Sell Stock III (Hard)

题目描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
思路
难点在于只能交易两次。

方法一：普通递归

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices==null || prices.length==0){
  4.             return 0;
  5.         }
  6.         return profit(prices, 0, 0, 0);
  7.     }
  8.     public int profit(int[]prices,int index, int way, int count){
  9.         if(index==prices.length || count==2){
  10.             return 0;
  11.         }
  12.         int x = 0, y=0;
  13.         x = profit(prices, index+1, way, count); //保持不动
  14.         //way有两种状态,0不持有，1持有
  15.         if(way==0){
  16.             y = profit(prices, index+1, 1, count) - prices[index];
  17.         }else{
  18.             y = profit(prices, index+1, 0, count+1) + prices[index];
  19.         }
  20.         return Math.max(x,y);
  21.     }
  22. }

方法2：备忘录+递归

  1. class Solution {
  2.     //定义Key
  3.     class Key{
  4.         int index;
  5.         int way;
  6.         int count;
  7.         public Key(int index, int way, int count){
  8.             this.index = index;
  9.             this.way = way;
  10.             this.count = count;
  11.         }
  12.         //这里需要实现自定义的equals和hashCode函数
  13.         public int hashCode() {
  14.             return this.index + this.way + this.count;
  15.         }
  16.         public boolean equals(Object obj) {
  17.             Key other = (Key)obj;
  18.             if(index==other.index && way==other.way && count==other.count) {
  19.                 return true;
  20.             }
  21.             return false;
  22.         }
  23.     }
  24.     public int maxProfit(int[] prices) {
  25.         if(prices==null || prices.length==0){
  26.             return 0;
  27.         }
  28.         HashMap<Key, Integer> map = new HashMap<>();
  29.         return profit(prices, map, 0, 0, 0);
  30.     }
  31.     public int profit(int[]prices, HashMap<Key, Integer> map, int index, int way, int count){
  32.         Key key = new Key(index,way,count);
  33.         if(map.containsKey(key)) {
  34.             return map.get(key);
  35.         }
  36.         if(index==prices.length || count==2){
  37.             return 0;
  38.         }
  39.         int x = 0, y=0;
  40.         x = profit(prices, map, index+1, way, count); //保持不动
  41.         //way有两种状态,0不持有，1持有
  42.         if(way==0){
  43.             y = profit(prices,map, index+1, 1, count) - prices[index];
  44.         }else{
  45.             y = profit(prices, map, index+1, 0, count+1) + prices[index];
  46.         }
  47.         map.put(key, Math.max(x,y));
  48.         return map.get(key);
  49.     }
  50. }

方法3：动态规划

多维书包
dp[x][i][j]：x表示第x天，i表示状态（持有或不持有），j表示个数，dp表示该状态下的最大利润。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices==null || prices.length==0){
  4.             return 0;
  5.         }
  6.         int n = prices.length;
  7.         int[][][] dp = new int[n][2][3];
  8.         dp[0][0][0] = 0;
  9.         dp[0][0][1] = 0;
  10.         dp[0][0][2] = 0;
  11.         dp[0][1][0] = -prices[0];
  12.         dp[0][1][1] = -prices[0];
  13.         dp[0][1][2] = -prices[0]; //注意初始化条件
  14.         for(int x=1; x<n; x++){
  15.             dp[x][0][0] = dp[x-1][0][0]; //不持有，卖出个数为0
  16.             dp[x][0][1] = Math.max(dp[x-1][0][1],dp[x-1][1][0]+prices[x]);  //不持有，卖出个数为1；
  17.             dp[x][0][2] = Math.max(dp[x-1][0][2],dp[x-1][1][1]+prices[x]);
  18.             dp[x][1][0] = Math.max(dp[x-1][0][0]-prices[x], dp[x-1][1][0]);
  19.             dp[x][1][1] = Math.max(dp[x-1][0][1]-prices[x], dp[x-1][1][1]);
  20.             dp[x][1][2] = dp[x-1][1][2];
  21.         }
  22.         int a = Math.max(dp[n-1][0][0],dp[n-1][0][1]);
  23.         int b = Math.max(dp[n-1][1][0],dp[n-1][1][1]);
  24.         return Math.max(Math.max(a,b),dp[n-1][0][2]);
  25.     }
  26. }

方法三的内存优化

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices==null || prices.length==0){
  4.             return 0;
  5.         }
  6.         int n = prices.length;
  7.         int[][] dp = new int[2][3];
  8.         dp[0][0] = 0;
  9.         dp[0][1] = 0;
  10.         dp[0][2] = 0;
  11.         dp[1][0] = -prices[0];
  12.         dp[1][1] = -prices[0];
  13.         dp[1][2] = -prices[0];
  14.         for(int x=1; x<n; x++){
  15.              //不持有，卖出个数为0，dp[0][0],dp[1][2]不变
  16.             dp[0][2] = Math.max(dp[0][2],dp[1][1]+prices[x]); 
  17.             dp[1][1] = Math.max(dp[0][1]-prices[x], dp[1][1]);
  18.             dp[0][1] = Math.max(dp[0][1],dp[1][0]+prices[x]);  //不持有，卖出个数为1；
  19.             dp[1][0] = Math.max(dp[0][0]-prices[x], dp[1][0]);   
  20.         }
  21.         int a = Math.max(dp[0][0],dp[0][1]);
  22.         int b = Math.max(dp[1][0],dp[1][1]);
  23.         return Math.max(Math.max(a,b),dp[0][2]);
  24.     }
  25. }

方法四：另一种动态规划方法

跟三维数组的有点类似，在三维数组中我们定义了交易次数、买卖状态。 因为交易次数和买卖状态都是常数个，所以我们把这两者整合到一起了。进而将三维数组转化为二维数组。

  • dp[i][0] 不持有，0次
  • dp[i][1] 持有，0次
  • dp[i][2] 不持有，1次
  • dp[i][3] 持有，1次
  • dp[i][4] 不持有，2次
    1. class Solution {
    2.   public int maxProfit(int[] prices) {
    3.       //dp[i][0] 不持有，0次
    4.       // dp[i][1] 持有，0次
    5.       // dp[i][2] 不持有，1次
    6.       // dp[i][3] 持有，1次
    7.       // dp[i][4] 不持有，2次
    8.       if(prices==null || prices.length<1){
    9.           return 0;
    10.       }
    11.       int len = prices.length;
    12.       int[][] dp = new int[len][5];
    13.       dp[0][0] = 0;
    14.       dp[0][1] = -prices[0];
    15.       dp[0][2] = 0;
    16.       dp[0][3] = -prices[0];
    17.       dp[0][4] = 0;
    18.       for(int i=1; i<len; i++){
    19.           dp[i][0] = dp[i-1][0];
    20.           dp[i][1] = Math.max(dp[i-1][1], dp[i][0]-prices[i]);
    21.           dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]+prices[i]);
    22.           dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2]-prices[i]);
    23.           dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3]+prices[i]);
    24.       } 
    25.       int a = Math.max(dp[len-1][0], dp[len-1][1]);
    26.       int b = Math.max(dp[len-1][2], dp[len-1][3]);
    27.       return Math.max(Math.max(a,b),dp[len-1][4]);
    28.   }
    29. }

    方法四的内存优化

    1. class Solution {
    2.   public int maxProfit(int[] prices) {
    3.       //dp[i][0] 不持有，0次
    4.       // dp[i][1] 持有，0次
    5.       // dp[i][2] 不持有，1次
    6.       // dp[i][3] 持有，1次
    7.       // dp[i][4] 不持有，2次
    8.       if(prices==null || prices.length<1){
    9.           return 0;
    10.       }
    11.       int len = prices.length;
    12.       int[] dp = new int[5];
    13.       dp[0] = 0;
    14.       dp[1] = -prices[0];
    15.       dp[2] = 0;
    16.       dp[3] = -prices[0];
    17.       dp[4] = 0;
    18.       for(int i=1; i<len; i++){
    19.           dp[4] = Math.max(dp[4], dp[3]+prices[i]);
    20.           dp[3] = Math.max(dp[3], dp[2]-prices[i]);
    21.           dp[2] = Math.max(dp[2], dp[1]+prices[i]);
    22.           dp[1] = Math.max(dp[1], dp[0]-prices[i]);
    23.       } 
    24.       int a = Math.max(dp[0], dp[1]);
    25.       int b = Math.max(dp[2], dp[3]);
    26.       return Math.max(Math.max(a,b),dp[4]);
    27.   }
    28. }
    结果
    image.png

    188. Best Time to Buy and Sell Stock IV (Hard)

    题目描述
    给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
    设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
    注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
    示例
    输入：k = 2, prices = [3,2,6,5,0,3]
    输出：7
    解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
    随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
    思路
    同上题相同，只不过2变为k，分单双数表示持有或不持有。
    1. class Solution {
    2.   public int maxProfit(int k, int[] prices) {
    3.       if(prices==null || prices.length==0){
    4.           return 0;
    5.       }
    6.       int len = prices.length;
    7.       //k单数表示持有，双数表示不持有
    8.       int[][] dp= new int[len][2*k+1];
    9.       //初始化
    10.       for(int i=0; i<2*k+1; i++){
    11.           if(i%2==0){
    12.               dp[0][i] = 0;
    13.           }else{
    14.               dp[0][i] = -prices[0];
    15.           }
    16.       }
    17.       for(int i=1; i<len; i++){
    18.           dp[i][0] = dp[i-1][0];
    19.           for(int j=1; j<2*k+1; j++){
    20.               if(j%2==0){
    21.                   dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]+prices[i]);
    22.               }else{
    23.                   dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]-prices[i]);
    24.               }
    25.           }
    26.       }
    27.       int Max = 0;
    28.       for(int i=1; i<2*k+1; i++){
    29.           if(dp[len-1][i]>Max){
    30.               Max = dp[len-1][i];
    31.           }
    32.       }
    33.       return Max;
    34.   }
    35. }

    内存优化

    1. class Solution {
    2.   public int maxProfit(int k, int[] prices) {
    3.       if(prices==null || prices.length==0){
    4.           return 0;
    5.       }
    6.       int len = prices.length;
    7.       //k单数表示持有，双数表示不持有
    8.       int[] dp= new int[2*k+1];
    9.       //初始化
    10.       for(int i=0; i<2*k+1; i++){
    11.           if(i%2==0){
    12.               dp[i] = 0;
    13.           }else{
    14.               dp[i] = -prices[0];
    15.           }
    16.       }
    17.       for(int i=1; i<len; i++){
    18.           for(int j=2*k; j>0; j--){
    19.               if(j%2==0){
    20.                   dp[j] = Math.max(dp[j], dp[j-1]+prices[i]);
    21.               }else{
    22.                   dp[j] = Math.max(dp[j], dp[j-1]-prices[i]);
    23.               }
    24.           }
    25.       }
    26.       int Max = 0;
    27.       for(int i=1; i<2*k+1; i++){
    28.           if(dp[i]>Max){
    29.               Max = dp[i];
    30.           }
    31.       }
    32.       return Max;
    33.   }
    34. }
    结果
    image.png