LeetCode 122：买卖股票的最佳时机 II

链接

题目：

思路：动态规划

题目框架

上一题最大交易次数K=1，而此题不限制K，即K为无穷，
则两个状态转移方程：

• 今天没有：昨天也没有 + 昨天有、卖了
• 今天持有：昨天也持有 + 昨天没有、买了

由于数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：

Java实现：

注意：
代码部分和上一题121几乎一样，
区别在于 求今天有时， 昨天没有、今天买了是 dp[i-1][0]-prices[i] ，符合逻辑；
而121题是 -prices[i] ！！！

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2];
        // base case
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        // 遍历状态
        for(int i=1;i<n;i++){
            //今天没有： 昨天没有 + 昨天有、卖了
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i] );
            //今天有：昨天有 + 昨天没有、买了
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i] );
        }
        return dp[n-1][0];
    }
}