matteo's coding field.

LeetCode.309 Best Time to Buy and Sell Stock with Cooldown

字数统计: 187阅读时长: 1 min
2019/08/15 Share

一段时间没做题了，发现真的没有天赋

题意
  • 还是买卖股票，不限次数，但是卖出后第二天不能做任何交易
    解法
  • 感觉是dp吧
  • 双重循环，i表示买入，j表示卖出，第j天时的最大收益为
  1. 当天未交易的结果dp[j - 1]
  2. 当天完成交易的结果prices[j] - prices[i] + dp[i-2]
  3. 非i天买入，j天时的结果dp[j]
  • 3种情况取最大值
    class Solution {
  public int maxProfit(int[] prices) {
      if (prices.length < 2) {
          return 0;
      }
      int dp[] = new int[prices.length];
      for (int i = 0; i < prices.length - 1; i++) {
          for (int j = i + 1; j < prices.length; j++) {
              dp[j] = Math.max(Math.max(dp[j], dp[j - 1]), (prices[j] - prices[i]) + (i > 1?dp[i-2]:0));
          }
      }
      return dp[prices.length - 1];
  }
}

原文作者：Matteo

原文链接：http://tlzxsun.github.io/2019/08/15/LeetCode-309-Best-Time-to-Buy-and-Sell-Stock-with-Cooldown/

发表日期：August 15th 2019, 7:10:09 pm

更新日期：August 15th 2019, 7:10:10 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题意
  2. 2. 解法
Total : 69
2019
LeetCode