526互联

状态机DP，力扣188. 买卖股票的最佳时机 IV

发布时间 2023-10-03 19:01:54作者: 深情的山鸡

状态机DP，力扣188. 买卖股票的最佳时机 IV

整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。一次只能参与一笔交易，最多可以进行 k 笔交易，求最大利润。

  • 确定状态f[n+1][k+2][2]，f[i][j][0]、f[i][j][1]分别表示前i天最多进行j次交易，且在第i天时 未持有股票/持有股票 所能获得的最大利润

    • i位置的取值为0~n-1，在递推式中需要用到i-1的状态，所以插入一个起始状态-1，由于下标无法表示-1所以让所有状态后移一位，总状态个数为n+1个
    • j位置的取值为0~k，k+1个状态，在递推式中需要用到j-1的状态，所以插入一个起始状态-1，由于下标无法表示-1所以让所有状态后移一位，总状态个数为k+2个
    • 结束状态：f[n][k + 1][0] = max(f[n][k + 1][0],f[n][k + 1][1])

  • 递推式：

    • f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][1] + prices[i - 1]);
    • f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - prices[i - 1]);

  • 初始化（边界条件），两种初始状态：1.合理初始状态=0 2.非法初始状态=-INF

    • f[·][0][·] = -INF，f[·][0][·]表示原先的f[·][-1][·]，j为-1时此状态为非法状态设为-INF。
    • f[0][j][0] = 0，f[0][j][0]表示第0天未持有任何股票进行j次交易的利润为0。
    • f[0][j][1] = -INF，f[0][j][1]表示原先的f[-1][j][1]，i取-1表示为非法状态设为-INF。

  • 状态机表示

Code

int maxProfit(int k, vector<int> &prices)
{
    int n = prices.size(), f[n + 1][k + 2][2];
    memset(f, -0x3f, sizeof(f));
    for (int i = 1; i <= k + 1; i++)
        f[0][i][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k + 1; j++)
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][1] + prices[i - 1]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j][0] - prices[i - 1]);
        }
    return f[n][k + 1][0];
}

思路参考b站灵茶山艾府