目录

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

思路

1、确定dp数组以及下标含义

2、确定递推公式

3、初始化dp数组

4、遍历顺序

买卖股票的最佳时机|||

使用二维数组进行推导

使用一维数组进行推导

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

思路

买卖股票的最佳时机IV

使用二维dp数组进行推导

使用一维dp数组进行推导

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

题目链接：力扣

思路

        这道题目确实情况更加的复杂，但是原理其实和前面的买入股票的题目都是差不多的，数组上的元素代表的就是手中钱的最大值，然后推算出各种情况的最大值，最后可以得到获得利润的最大值

        最多买卖两次，这意味着可以买卖一次，也可以买卖两次，也可以不买卖

1、确定dp数组以及下标含义

 对股票来说，一天可能有五种状态：

• 没有操作
• 第一次买入
• 第一次卖出
• 第二次买入
• 第二次卖出

i 表示天数，在第几天，j 为（0，4）五种状态，dp[i][j] 代表：第 i 天状态 j 手中的最大现金数

2、确定递推公式

dp[i][0] 代表没有操作，所以是从 dp[i - 1][0] 中推导而来

dp[i][1] 代表第一次买入，可以由两种状态推导而来
        如果第 i 天没有操作 ，那么就是前面的状态，dp[i][1] = dp[i - 1][1]
        如果第 i 天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
        选择其中现金数最大的状态，dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1])

dp[i][2] 代表第一次卖出，可以由两种状态推导而来
        如果第 i 天没有操作，那么就是前面的状态，dp[i][2] = dp[i - 1][2]
        如果第 i 天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
        选择其中现金数最大的状态，dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

dp[i][3] 代表第二次买入，可以由两种状态推导而来
        如果第 i 天没有操作，那么就是前面的状态，dp[i][3] = dp[i - 1][3]
        如果第 i 天买入股票了，那么dp[i][3] = dp[i - 1][2] - prices[i]
        选择其中现金数最大的状态，dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])

dp[i][4]代表第二次卖出，可以由两种状态推导而来
        如果第 i 天没有操作，那么就是前面的状态，dp[i][4] = dp[i - 1][4]
        如果第 i 天卖出股票了，那么dp[i][4] = dp[i - 1][3] + prices[i]
        选择其中现金数最大的状态，dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

3、初始化dp数组

        从递推公式可以看出，都是由dp[i-1][0-4]的状态推导而来的，所以 dp[0][0]、dp[0][1]、dp[0][2]、dp[0][3]、dp[0][4] 都需要进行初始化

第 0 天，没有操作的的话，手中的现金就是0，即 dp[0][0] = 0;

第 0 天，第一次买入的话，手中的现金就是0 - prices[0]，即 dp[0][1] = -prices[0];

第 0 天，第一次卖出的话，没有可卖出的，手中的现金就是0，即dp[0][2] = 0;

第 0 天，第二次买入的话，手中的现金就是0 - prices[0]，即dp[0][3] = -prices[0];

第 0 天，第二次卖出的话，没有可卖出的，手中的现金就是0，即dp[0][4] = 0;

4、遍历顺序

        从前向后遍历

买卖股票的最佳时机|||

使用二维数组进行推导

class Solution {public int maxProfit(int[] prices) {// 创建dp数组int[][] dp = new int[prices.length][5];// 初始化dp数组dp[0][1] = -prices[0];dp[0][3] = -prices[0];// 推导dp数组for (int i = 1; i < prices.length; 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[prices.length - 1][4];}
}

使用一维数组进行推导

class Solution {public int maxProfit(int[] prices) {// 创建dp数组int[] dp = new int[5];// 初始化dp数组dp[1] = -prices[0];dp[3] = -prices[0];// 推导dp数组for (int i = 1; i < prices.length; 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];}
}

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

题目链接：力扣

思路

        这道题目其实是上一道题目的进阶版，将最多可买卖两次，进阶成最多可买卖k次，其实就是找到上道题目的规律，运用到这道题目中

对二维数组来说

• 首先，就是创建dp数组

  • // 最多买卖两次
    // 创建dp数组
    int[][] dp = new int[prices.length][5];// 最多买卖k次
    // 创建dp数组
    int[][] dp = new int[prices.length][2*k + 1];

• 其次就是初始化数组

  • // 最多买卖2次
    // 初始化dp数组
    dp[1] = -prices[0];
    dp[3] = -prices[0];// 最多买卖k次
    // 初始化dp数组
    for (int i = 1; i < 2*k; i += 2) {dp[0][i] = -prices[0];
    }
    

• 最后就是递推阶段

  • // 最多买卖2次
    // 推导dp数组
    for (int i = 1; i < prices.length; 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]);
    }// 最多买卖k次
    // 推导dp数组
    for (int i = 1; i < len; i++) {for (int j = 0; j < 2*k - 1; j+=2) {dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]);dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]);}
    }
    

买卖股票的最佳时机IV

使用二维dp数组进行推导

class Solution {public int maxProfit(int k, int[] prices) {if (k == 0 || prices.length == 0) {return 0;}// 创建dp数组int len = prices.length;int[][] dp = new int[len][2*k + 1];// 初始化dp数组for (int i = 1; i < 2*k; i += 2) {dp[0][i] = -prices[0];}// 推导dp数组for (int i = 1; i < len; i++) {for (int j = 0; j < 2*k - 1; j+=2) {dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]);dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]);}}return dp[len-1][2*k];}
}

使用一维dp数组进行推导

class Solution {public int maxProfit(int k, int[] prices) {if (k == 0 || prices.length == 0) {return 0;}// 创建dp数组int[] dp = new int[2 * k + 1];// 初始化dp数组for (int i = 1; i < 2*k + 1; i+=2) {dp[i] = -prices[0];}// 推导dp数组for (int i = 1; i < prices.length; i++) {for (int j = 0; j < 2*k - 1; j+=2) {dp[j + 1] = Math.max(dp[j + 1],dp[j]-prices[i]);dp[j + 2] = Math.max(dp[j + 2],dp[j+1]+prices[i]);}}return dp[2*k];}
}