LeetCode-买卖股票的最佳时机 II

语言: CN / TW / HK

算法记录

LeetCode 题目:

  给你一个整数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格,返回你能获得的 最大 利润 。


说明

一、题目

  在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

二、分析

  • 这种题型一看就和动态规划搭边的,关键是我们要怎么才能建立动态规划的转移方程。
  • 首先我们来分析题目中的信息,在第 i 天的时候会有一股票价格为 prices[i] ,我们可以选择买入或者卖出,那也就意味着一旦卖出,我们手里的资金就会增加当天的价格,卖出我们的资金就会减去当天的价格。
  • 我们再来分析什么情况才能进行卖出和买进,根据题意我们只能携带一只股票,也就是说要门有一股要么什么也没有。那也就是说只有前一天我们手里存在一股我们今天才能卖出去,前一天没有股票我们今天才能买进,到这里基本的状态我们已经明白了,下面来设计转移方程。
  • DP 数组设计为 N * 2 的长度,表示为第 i 天没有持有股票的最大收益和持有股票的最大收益。
  • 转移方程:当天持有股票的状态肯定由前一天没有持有股票今天购买或者是前一天持有股票今天没有购买转移,收益最高取最大值;当天没有持有股票肯定由前一天持有股票今天卖出或者是前一天没有持有股票今天没有购买转移,收益最高取最大值。

java class Solution { 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][1] + prices[i], dp[i - 1][0]); dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]); } return dp[n - 1][0]; } }


总结

分析题意构建状态转移方程。