买卖股票的最佳时机 IV (leetcode 188)

leetcode系列

文章目录

• 一、核心操作
• 二、外层配合操作
• 三、核心模式代码
• 总结

一、核心操作

1. 对于每一次处于买入和卖出状态，都依赖于上一次买入或卖出的状态，而买入就是在上一次卖出的基础上减去当天股票的价格，卖出就是在上一次买入的基础上加上当天的股票价格，所以一共要设置2*k+1个状态，其中还有一个是什么都不干的状态，初值全部为0
2. 设置初值：只要是奇数状态则设置为-prices[0]
3. 大循环为遍历每天的价格，小循环为更新dp数组

提示：小白个人理解，如有错误敬请谅解！

二、外层配合操作

1. 无

三、核心模式代码

代码如下：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=2*k+1;
        vector<int> dp(vector<int>(n,0));
        for(int i=1;i<n;i+=2)
        {
            dp[i]=-prices[0];
        }
        for(int i=1;i<prices.size();i++)
        {
            for(int j=1;j<n;j++)
            {
                if(j%2)
                {
                    dp[j]=max(dp[j],dp[j-1]-prices[i]);
                }
                else 
                {
                    dp[j]=max(dp[j],dp[j-1]+prices[i]);
                }
                // cout<<dp[j]<<" ";
            }
            // cout<<endl;
        }
        return dp[n-1];
    }
};

总结

1. 当循环只操作奇数位时，一定要i+=2,设置为i+2没有任何作用，且小循环时一定不能让j超过数组大小！！！