Best Time to Buy And Sell Stock II

题目链接：题目描述

这道题我们首先考虑动态规划来写。

定义dp[i][0]为第i天手上没有股票；dp[i][1]为第i天手上持有股票。

那么，考虑dp[i][0]的状态转移方程：这一天没有持有股票，那么有可能前一天也没有持有股票，所以就是dp[i-1][0]；也有可能，前一天是持有了股票的,即dp[i-1][1]，持有了股票的话，我们就要考虑在第i天把它卖出去，那么我就可以拿到prices[i]的钱，最后二者要取最大值。所以就是dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]).同理，对于dp[i-1][1]而言，有可能前面那一天我也持有股票；也有可能没有持有，而第i天我是买了股票的，所以要把花钱买prices[i]的股票，所以状态转移方程就是：dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]).

好了，现在我们来看看初始值，那么，第0天没有持有股票，所以dp[0][0] = 0.而dp[0][1],表示第0天就有股票了，这刚开始我肯定是没钱的，所以就是0-prices[i]=-prices[i].

下面是代码：

 1 public int maxProfit(int[] prices) {
 2         int n = prices.length;
 3         int[][] dp = new int[n][n];
 4         dp[0][0] = 0;
 5         dp[0][1] = -prices[0];
 6         for (int i = 1; i < n; ++i) {
 7             dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
 8             dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
 9         }
10         return dp[n-1][0];
11 }

 这样开数组，仔细分析我们会发现其实没有必要，因为每一天的状态都只跟前一天的状态有关。因此我们考虑使用几个变量来代替数组：

代码：

 1 public int maxProfit(int[] prices) {
 2         int profitOut = 0;
 3         int profitIn = -prices[0];
 4         for (int i = 0; i < prices.length; ++i) {
 5             int out = Math.max(profitOut, profitIn+prices[i]);
 6             int in = Math.max(profitIn, profitOut-prices[i]);
 7             profitOut = out;
 8             profitIn = in;
 9         }
10         return profitOut;
11 }

 大功告成！