LeetCode 123买卖股票的最佳时机-iii 188买卖股票的最佳时机-iv | 代码随想录25期训练营day50

动态规划算法8

LeetCode 123 买卖股票的最佳时机-iii 2023.12.13

• 题目链接
• 代码随想录讲解[链接]
  

int maxProfit(vector<int>& prices) {
    //1确定dp二维数组
    //dp[i][0]表示遍历到第i天时第一次持有股票的当前收入;dp[i][1]表示遍历到第i天时第一次未持有股票的当前收入
    //dp[i][2]表示遍历到第i天时第二次持有股票的当前收入;dp[i][3]表示遍历到第i天时第二次未持有股票的当前收入
    vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
    //3初始化，第一天第一次与第二次持有股票的收入为-prices[0]，其他值为0
    dp[0][0] = -prices[0];
    dp[0][2] = -prices[0];
    //2确定递推公式，4确定遍历顺序
    for (int i = 1; i < prices.size(); i++)
    {
        //第i天第一次持有股票的收入=max(股票不卖(上一天第一次持有股票的收入)，第一次买完今天的股票的收入)
        dp[i][0] = max(dp[i-1][0], -prices[i]);
        //第i天第一次未持有股票的收入=max(上一天第一次未持有股票的收入，今天第一次卖股票的收入）
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);
        //第i天第二次持有股票的收入=max(股票不卖(上一天第二次持有股票的收入)，第二次买完今天的股票的收入)
        dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i]);
        //第i天第二次未持有股票的收入=max(上一天第二次未持有股票的收入，今天第二次卖股票的收入）
        dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i]);
    }
    //输出答案为最后一天第二次未持有股票的结果
    return dp[prices.size()-1][3];
}

LeetCode 188 买卖股票的最佳时机-iv 2023.12.13

• 题目链接
• 代码随想录讲解[链接]
  

int maxProfit(int k, vector<int>& prices) {
    //1确定dp二维数组
    //dp[i][0]表示遍历到第i天时第一次持有股票的当前收入;dp[i][1]表示遍历到第i天时第一次未持有股票的当前收入
    //dp[i][2*j]表示遍历到第i天时第j+1次持有股票的当前收入;dp[i][2*j+1]表示遍历到第i天时第j+1次未持有股票的当前收入
    vector<vector<int>> dp(prices.size(), vector<int>(2*k, 0));
    //3初始化，第一天第一次到第k次持有股票的收入为-prices[0]，其他值为0
    for (int i = 0; i < 2*k; i += 2)
        dp[0][i] = -prices[0];
    //2确定递推公式，4确定遍历顺序
    for (int i = 1; i < prices.size(); i++)
    {
        for (int j = 0; j < 2*k; j += 2)
        {
            //第i天第一次持有股票的收入=max(股票不卖(上一天第一次持有股票的收入)，第一次买完今天的股票的收入)
            if(j == 0)
                dp[i][j] = max(dp[i-1][j], -prices[i]);
            //第i天第j次持有股票的收入=max(股票不卖(上一天第j次持有股票的收入)，第j次买完今天的股票的收入)
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i]);
            //第i天第j次未持有股票的收入=max(上一天第j次未持有股票的收入，今天第j次卖股票的收入）
            dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]+prices[i]);
        }
    }
    //输出答案为最后一天第k次未持有股票的结果
    return dp[prices.size()-1][2*k-1];
}