• Day50【动态规划】123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV

    123.买卖股票的最佳时机III

    力扣题目链接/文章讲解

    视频讲解

    1、确定 dp 数组下标及值的含义 

    先想想本题 dp 应该怎么定义，别忘了之前说的，dp 数组的下标能够表示状态

    在本道股票问题中，某个状态需要描述在某天，及是否持有股票，及当前已经买过多少次了（因为本题最多能够买卖两次，需要关注买卖次数）

    因此我们定义 dp 数组下标及值含义：

    dp[i][0]：下标表示在第 i 天，买入过 0 次股票，值为当前状态下的最大利润

    dp[i][1]：下标表示在第 i 天，买入过 1 次股票且持有股票，值为当前状态下的最大利润

    dp[i][2]：下标表示在第 i 天，买入过 1 次股票且未持有股票，值为当前状态下的最大利润

    dp[i][3]：下标表示在第 i 天，买入过 2 次股票且持有股票，值为当前状态下的最大利润

    dp[i][4]：下标表示在第 i 天，买入过 2 次股票且未持有股票，值为当前状态下的最大利润

    通过第一个下标 i 描述在哪一天，第二个下标取 0 到 4 中的值表示在某天的股票持有情况及历史买入情况，这样通过两个下标就能够描述所有状态了

    2、确定递推公式 

    需要分别思考 dp[i][0]、dp[i][1]、dp[i][2]、dp[i][3]、dp[i][4] 应该怎么推

    dp[i][0]：没买过股票的最大利润，为 0

    dp[i][1]：在第 i 天已经买入过一次股票且持有股票的最大利润，考虑怎么从前一天转移到当前状态。可能是在第 i 天第一次买入股票（dp[i - 1][0] - prices[i]），也可能是第 i - 1 天的时候就已经持有第一次买入的股票了（dp[i - 1][1]）。因为取最大利润，即 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])

    dp[i][2]：在第 i 天已经买入过一次股票且未持有股票的最大利润，考虑怎么从前一天转移到当前状态。可能是在第 i 天卖出了第一次买的股票（dp[i - 1][1] + prices[i]），也可能是第 i - 1 天的时候就已经卖出过第一次买入的股票了（dp[i - 1][2]）。因为取最大利润，即 dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

    dp[i][3]：在第 i 天已经买入过两次股票且持有股票的最大利润，考虑怎么从前一天转移到当前状态。可能是在第 i 天第二次买入股票（dp[i - 1][2] - prices[i]），也可能是第 i - 1 天的时候就已经持有第二次买入的股票了（dp[i - 1][3]）。因为取最大利润，即 dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])

    dp[i][4]：在第 i 天已经买入过两次股票且未持有股票的最大利润，考虑怎么从前一天转移到当前状态。可能是在第 i 天卖出了第二次买的股票（dp[i - 1][3] + prices[i]），也可能是第 i - 1 天的时候就已经卖出过第二次买入的股票了（dp[i - 1][4]）。因为取最大利润，即 dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4]) 

    3、dp 数组初始化

    根据递推公式，第 i 天的 dp 值都是从第 i - 1 天的 dp 值推导出来的，我们需要初始化dp[0][j]

    dp[0][0] = 0（第 0 天啥也不干） 

    dp[0][1] = -prices[0]（第 0 天买入股票）

    dp[0][2] = 0（第 0 天当天买入当天卖出）

    dp[0][3] = -prices[0]（第 0 天当前买入又卖出后，再买入）

    dp[0][4] = 0（第 0 天两次买入卖出）

    4、确定遍历顺序

    从递推公式可以看出 dp[i] 都是由 dp[i - 1] 推导出来的，那么一定是从前向后遍历

    5、打印 dp 数组验证

    代码如下

    1. class Solution {
    2. public:
    3.     int maxProfit(vector<int>& prices) {
    4.         // 定义dp数组下标及值含义，dp[i][j]表示第i天，j取0-4表示5种不同的持有股票状态，dp[i][j]值表示当前状态最大利润
    5.         vectorint> > dp(prices.size(), vector<int>(5));
    6.  
    7.         // 递推公式
    8.         // dp[i][0] = 0    // 这个其实可以不考虑
    9.         // dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])
    10.         // dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])
    11.         // dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3])
    12.         // dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4])
    13.  
    14.         // 初始化dp[0][j]
    15.         dp[0][0] = 0;
    16.         dp[0][1] = -prices[0];
    17.         dp[0][2] = 0;
    18.         dp[0][3] = -prices[0];
    19.         dp[0][4] = 0;
    20.  
    21.  
    22.         // 遍历填充dp数组，i从小到大遍历
    23.         for (int i = 1; i < prices.size(); ++i) {
    24.             dp[i][0] = 0;
    25.             dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]);
    26.             dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2]);
    27.             dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3]);
    28.             dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4]);
    29.         }
    30.  
    31.         // return *max_element(dp[prices.size() - 1].begin(), dp[prices.size() - 1].end());
    32.         return dp[prices.size() - 1][4];
    33.     }
    34. };

    注意最后的返回值，返回值表明两次卖出的状态现金最大一定是最后一次卖出。因为如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。

    所以最终最大利润是 dp[prices.size() - 1][4]

    本题同样能够利用滚动数组优化，滚动数组仅维护某一天的几种状态。代码如下

    关键就是更新滚动数组 dp 值时，需要正确对应到原二维 dp 数组中上一层的 dp 值

    1. class Solution {
    2. public:
    3.     int maxProfit(vector<int>& prices) {
    4.         // 滚动数组仅需维护某一天的状态
    5.         vector<int> dp(5);
    6.  
    7.         // 初始化原二维dp数组的第一行（第一天）dp[0][j]
    8.         dp[0] = 0;
    9.         dp[1] = -prices[0];
    10.         dp[2] = 0;
    11.         dp[3] = -prices[0];
    12.         dp[4] = 0;
    13.  
    14.         // 遍历填充dp数组，i从小到大遍历，表示一行一行填充原二维dp数组，即一天一天更新
    15.         for (int i = 1; i < prices.size(); ++i) {
    16.             // 注意，等式右边对应的二维dp数组中的上一层的值
    17.             dp[4] = max(dp[3] + prices[i], dp[4]);
    18.             dp[3] = max(dp[2] - prices[i], dp[3]);    // 此时dp[4]已经对应到当前层的dp值了，赋值dp[4]到dp[0]的顺序不能颠倒
    19.             dp[2] = max(dp[1] + prices[i], dp[2]);
    20.             dp[1] = max(dp[0] - prices[i], dp[1]);
    21.             dp[0] = 0;
    22.         }    // 遍历完成后，滚动数组存的是原dp数组最后一天的几种状态
    23.  
    24.         return dp[4];
    25.     }
    26. };

    188.买卖股票的最佳时机IV 

    力扣题目链接/文章讲解

    视频讲解

    1、定义 dp 数组下标及值含义

    dp[i][1]：下标表示在第 i 天，买入过 1 次股票且持有股票，值为当前状态下的最大利润

    dp[i][2]：下标表示在第 i 天，买入过 1 次股票且未持有股票，值为当前状态下的最大利润

    dp[i][3]：下标表示在第 i 天，买入过 2 次股票且持有股票，值为当前状态下的最大利润

    dp[i][4]：下标表示在第 i 天，买入过 2 次股票且未持有股票，值为当前状态下的最大利润

    ……  

    通过第二个维度的值来表示在某一天的股票持有及历史购买情况 

    题目要求是至多有 k 笔交易，即最多可以买入过 k 次，在某买入次数的前提下，有持有和未持有两种状态，即总共有 2 * k 种状态（可以不考虑买入过 0 次的状态），即定义 dp 数组

    vectorint>> dp(prices.size(), vector<int>(2 * k + 1, 0));

    2、确定递推公式

    达到 dp[i][1] 状态，有两个具体操作：

    • 操作一：第 i 天买入股票了，那么 dp[i][1] = dp[i - 1][0] - prices[i]
    • 操作二：第 i 天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

    选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);

    同理 dp[i][2] 也有两个操作：

    • 操作一：第 i 天卖出股票了，那么 dp[i][2] = dp[i - 1][1] + prices[i]
    • 操作二：第 i 天没有操作，沿用前一天未持有股票的状态，即：dp[i][2] = dp[i - 1][2]

    所以 dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

    同理可以类比剩下的状态，代码如下：

    1. for (int j = 0; j < 2 * k - 1; j += 2) {
    2.     dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);    // 持有股票
    3.     dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);    // 未持有股票
    4. }

    3、dp 数组初始化

    dp[0][j] 当 j 为偶数的时候都初始化为 0（表示当天买入又卖出）

    dp[0][j] 当 j 为奇数的时候都初始化为 -prices[0]（表示当天买入卖出了几轮后，再买入）

    4、 确定遍历顺序

    5、打印 dp 数组验证

    代码如下

    1. class Solution {
    2. public:
    3.     int maxProfit(int k, vector<int>& prices) {
    4.  
    5.         if (prices.size() == 0) return 0;
    6.         vectorint>> dp(prices.size(), vector<int>(2 * k + 1, 0));
    7.         for (int j = 0; j < 2 * k + 1; ++j) {
    8.             if (j % 2) dp[0][j] = -prices[0];   // 持有股票
    9.             else dp[0][j] = 0; // 未持有股票
    10.         }
    11.         for (int i = 1;i < prices.size(); i++) {
    12.             for (int j = 0; j < 2 * k - 1; j += 2) {
    13.                 dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); // 持有股票
    14.                 dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); // 未持有股票
    15.             }
    16.         }
    17.         return dp[prices.size() - 1][2 * k];
    18.     }
    19. };

    当然有的解法是定义一个三维数组 dp[i][j][k]，第 i 天，买入过 j 次股票，k 表示是否持有股票的状态，从定义上来讲比较直观

    1. class Solution {
    2. public:
    3.     int maxProfit(int k, vector<int>& prices) {
    4.         // dp[i][j][k]，索引号为i的那天，买入过j次股票，k表示是否持有股票的状态
    5.         vectorint> > > dp(prices.size(), vectorint> >(k + 1, vector<int>(2, 0)));
    6.  
    7.         for (int j = 0; j <= k; ++j) {
    8.             dp[0][j][1] = -prices[0];   // 第0天，当持有股票，此时利润为-prices[0]
    9.             // 否则，当未持有股票，说明在第0天买卖了几轮，利润为0
    10.         }
    11.  
    12.         for (int i = 1; i < prices.size(); ++i) {   // 从第二天开始填充dp数组
    13.             for (int j = 1; j <= k; ++j) {  // j为0时表示一次也没买入过，利润肯定为0
    14.                 dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i]);  // 第i天，买入过j次股票且未持有状态
    15.                 dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i]);    // 第i天，买入过j次股票且持有状态
    16.             }
    17.         }
    18.         return dp[prices.size()-1][k][0];   // 一定是卖了股票后利润最大
    19.     }
    20. };

    回顾总结 

    灵活利用 dp 数组的下标描述所有状态 

  • 相关阅读:
    入坑 Node.js 1
    简单了解一下pinia的结构
    一文概括AxureRP的优缺点和替代软件
    ai批量剪辑矩阵无人直播一站式托管系统源头技术开发
    华为云云耀云服务器L实例评测｜带宽，磁盘，CPU，内存以及控制台监控测试
    选择屏幕2
    《C++ primer plus》精炼（OOP部分）——对象和类（7）
    现在软件开发app制作还值得做吗
    力扣热题100——一刷day01
    Redis的使用--集群模式
  • 原文地址：https://blog.csdn.net/qq_41657851/article/details/130840167