LeetCode122. 买卖股票的时机 II

LeetCode122. 买卖股票的时机 II思路:
动态规划

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

 递推式:

   ● 第i-1天就持有股票,保持现状,dp[i][0]=dp[i-1][0]

    ● 第i天买入股票,就是第i-1天不持有股票最大利润-price[i]:dp[i][0]=dp[i-1][1]-price[i]

        dp[i][0]选最大的,dp[i][0]=max(dp[i-1][0],dp[i-1][1]-price[i])

 (2)如果第i天不持有股票,即dp[i][1]是第i天不持有股票获得的最多的现金

●如果第i天卖出,dp[i][1]=price[i]+dp[i-1][0]   

    理解:第i天卖出说明,第i-1天持有股票,获得收益为前i-1天的收益+第i天的收益

●如果第i天不卖出,说明已经卖出去,收益和第i-1天相同,dp[i][1]=dp[i-1][1]

     dp[i][1]取最大的,dp[i][1]=max(dp[i-1][1],price[i]+dp[i-1][0]);

上一篇:PAT乙级1030:完美数列 (25)-测试点5


下一篇:PAT_乙级 1017 A除以B (20 分)