当前位置： 移动技术网 > IT编程>数据库>Mysql > LeeCode 188 DP + 贪心

LeeCode 188 DP + 贪心

2020年07月15日  | 移动技术网IT编程  | 我要评论
题意

传送门 LeeCode 188

题解

dp[i][j][k]dp[i][j][k] 代表第 ii 天已经进行 jj 次交易且当前状态为 kk 时，可获得的最大利润。设未持有股票的状态为 00，持有股票的状态为 11，则递推式为

{dp[i][j][0]=max(dp[i−1][j][0],dp[i−1][j−1][1]+prices[i]dp[i][j][1]=max(dp[i−1][j][1],dp[i−1][j][0]−prices[i]\begin{cases} dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]+prices[i]\\ dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j][0]-prices[i]\\ \end{cases}

考虑到第一维状态转移总是 (i−1)−>i(i-1)->i，则 dpdp 可以压缩为二维。

kk 值可能过大，假如 kk 大于买卖股票的最大可能交易次数，此时最优解没有交易次数的限制，贪心地将每一段 [i,i+1](prices[i]<prices[i+1])[i,i+1](prices[i]<prices[i+1]) 的差值计入答案即可。

class Solution
{
#define inf 0x3f3f3f3f
public:
    int maxProfit(int k, vector<int> &prices)
    {
        int res = 0, n = prices.size();
        if (n == 0)
        {
        }
        else if (k >= n / 2)
        {
            for (int i = 0; i + 1 < n; i++)
            {
                if (prices[i + 1] - prices[i] > 0) res += prices[i + 1] - prices[i];
            }
        }
        else
        {
            vector<vector<int>> dp(k + 1, vector<int>(2, -inf));
            dp[0][0] = 0, dp[0][1] = -prices[0];
            for (int i = 1; i < n; i++)
            {
                dp[0][1] = max(dp[0][1], -prices[i]);
                for (int j = k; j >= 1; j--)
                {
                    dp[j][0] = max(dp[j][0], dp[j - 1][1] + prices[i]);
                    dp[j][1] = max(dp[j][1], dp[j][0] - prices[i]);
                }
            }
            for (int i = 0; i <= k; i++) res = max(res, dp[i][0]);
        }
        return res;
    }
};

本文地址：https://blog.csdn.net/neweryyy/article/details/107341254

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网