题解 | #牛群买卖计划II#

知识点

动态规划 线性

思路

这题是上一题的强化版本，不过只需要将3改为k即可。可以用dp[i][j][k]表示最大利润

f[i][j][k]， k取0或1，0表示手中无货，1表示手中有货，

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int n=prices.size();
        int dp[1005][1005][2];
        memset(dp,-0x3f,sizeof dp);

        for(int i=0;i<=n;i++)dp[i][0][0]=0;
        //int minx=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
           for(int j=1;j<=k;j++)
           {
            dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
            dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);
           }
        }
        int res=0;
        for(int i=0;i<=k;i++)res=max(dp[n][i][0],res);
        return res;
    }
};