当前位置：首页 > news >正文

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

news 来源：原创 2024/9/22 11:30:46

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

贪心法：

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

动态规划：版本一

// 解法1
class Solution {public int maxProfit(int[] prices) {if (prices == null || prices.length == 0) return 0;int length = prices.length;// dp[i][0]代表第i天持有股票的最大收益// dp[i][1]代表第i天不持有股票的最大收益int[][] dp = new int[length][2];int result = 0;dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < length; i++) {dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);}return dp[length - 1][1];}
}

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

class Solution {public int maxProfit(int[] prices) {int len = prices.length;int dp[][] = new int[2][2];dp[0][0] = - prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++){dp[i % 2][0] = Math.max(dp[(i - 1) % 2][0], - prices[i]);dp[i % 2][1] = Math.max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);}return dp[(len - 1) % 2][1];}
}

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

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

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

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

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

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

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

// 版本一
class Solution {public int maxProfit(int[] prices) {int len = prices.length;// 边界判断, 题目中 length >= 1, 所以可省去if (prices.length == 0) return 0;/** 定义 5 种状态:* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出*/int[][] dp = new int[len][5];dp[0][1] = -prices[0];// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润dp[0][3] = -prices[0];for (int i = 1; i < len; i++) {dp[i][1] = Math.max(dp[i - 1][1], -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[len - 1][4];}
}// 版本二: 空间优化
class Solution {public int maxProfit(int[] prices) {int[] dp = new int[4]; // 存储两次交易的状态就行了// dp[0]代表第一次交易的买入dp[0] = -prices[0];// dp[1]代表第一次交易的卖出dp[1] = 0;// dp[2]代表第二次交易的买入dp[2] = -prices[0];// dp[3]代表第二次交易的卖出dp[3] = 0;for(int i = 1; i <= prices.length; i++){// 要么保持不变，要么没有就买，有了就卖dp[0] = Math.max(dp[0], -prices[i-1]);dp[1] = Math.max(dp[1], dp[0]+prices[i-1]);// 这已经是第二次交易了，所以得加上前一次交易卖出去的收获dp[2] = Math.max(dp[2], dp[1]-prices[i-1]);dp[3] = Math.max(dp[3], dp[2]+ prices[i-1]);}return dp[3];}
}