力扣买股票的初始化问题

力扣官网评论很多，作为初刷题者，掌握套路很重要。
动态规划主要是①状态的定义②状态转移公式的推断。

把股票的系列刷了一遍，稍微难点的是123及188题，两个其实可以用同一个套路来解。虽然公式很容易就写出来了，但是初始条件却很难界定。

先贴代码，这段代码是123的代码，

public int maxProfit(int[] prices) {
        int k=2;
        k = Math.min(k, prices.length / 2);
        int[][][] dp = new int[prices.length][k+1][2];
        int ans = 0;
        for(int a = 0;a<=k;a++){
            dp[0][a][0] = 0;
            dp[0][a][1] = -prices[0];
        }
        for(int i=1;i<prices.length;i++){
            for(int j=1;j<=k;j++){
                dp[i][j][0] = Math.max(dp[i-1][j][1]+prices[i],dp[i-1][j][0]);
                dp[i][j][1] = Math.max(dp[i-1][j-1][0]-prices[i],dp[i-1][j][1]);
                int max = Math.max(dp[i][j][0],dp[i][j][1]);
                ans = Math.max(ans,max);
            }
        }
        return ans;
}

其中比较关键的一个是k的初始值设定。
初始值设定是，股票交易的次数不能跟数组长度（即天数）逻辑相违。dp数组第二维我设置的就是交易次数，i=n时，有买入j就计次1，直到卖出后再次买入j++，所以对第二维度的交易次数是不可能大于数组长度的1/2的。
其次就是对状态的初始化，这个主要是状态推断需要使用，我们可以将几个数代入

dp[i][j][0] = Math.max(dp[i-1][j][1]+prices[i],dp[i-1][j][0]);
dp[i][j][1] = Math.max(dp[i-1][j-1][0]-prices[i],dp[i-1][j][1]);

[1][1][0] needs [0][1][1],[0][1][0]
[1][1][1] needs [0][0][0],[0][1][1]

[1][2][0] needs [0][2][1],[0][2][0]
[1][2][1] needs [0][1][0],[0][2][1]

……

[1][k][0] needs [0][k][1],[0][k][0]
[1][k][1] needs [0][k][0],[0][k][1]

从以上可看出[0][1][0],[0][2][0]这种值从dp数组定义角度，代表着第一天交易k次，手上都不持有股票的情况。从原题题意来讲场景不存在，因为一天只能交易一次，这种时候计算dp[i][j][0]时，需要使dp[i-1][j][1]+prices[i]恒为答案，因为另一个选项dp[i-1][j][0]没有意义。
力扣里面很多解题思路会直接讲第0天无论交易多少次，持有为0的话都是0，大多的解题思路会根据这个理论直接将[0][k][0]设置为0。然后同理将[0][k][1]设为-prices[0]。但我觉得这种说法很敷衍，缺少前因后果，从代码角度无法支撑其他动态规划的题。

代码里是一个双循环，我们要确保i固定的情况下j无论多高（哪怕大于了i/2），保持的都是一个正确的值，而由于动态规划自底向上，我们只需要保证i=0这个维度的初始化（见上面needs后面的公式，只需要[0][k][0]和[0][k][1]即可），从这个角度来讲，要将[0][k][0]和[0][0][0]（即0）保持一致，[0][k][1]和[0][1][1]保持一致（即-prices[0]），就可以保证[1][k][0] 和[1][k][1]的正确性。因此设置了

        for(int a = 0;a<=k;a++){
            dp[0][a][0] = 0;
            dp[0][a][1] = -prices[0];
        }

至此即可。

最后编辑于：2021.03.09 11:15:05