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]; } }
