ToB企服应用市场:ToB评测及商务社交产业平台

标题: 代码随想录算法训练营day41｜动态规划part08 [打印本页]
作者: 自由的羽毛    时间: 2024-8-14 09:28
标题: 代码随想录算法训练营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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4