devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划(三) —— 股票投资系列问题总结_动态规划股票问题

作者：2023面试高手 | 2024-06-09 09:50:21

赞

踩

动态规划股票问题

前言

        Hello大家好，荔枝又来跟大家分享啦！这次荔枝带来的是有关动态规划中的股票投资问题的分析总结和样题对比，为了帮助大家进一步地去了解更多地体会荔枝也是详细的分析解题的步骤和思维。希望荔枝的总结能帮助到有需要的小伙伴吧哈哈哈~~~

文章目录

前言

一、Leecode121.买卖股票的最佳时机

1.1 题目分析

1.2 题解示例

二、Leecode122.买卖股票的最佳实际II

2.1 题目分析

2.2 题解示例

三、Leecode123.买卖股票的最佳时机III

3.1 题目分析

3.2 题解示例

四、买卖股票的最佳时机IV

4.1 题目分析

4.2 题解示例

五、 Leecode309.最佳买卖股票时机含冷冻期

5.1 题目分析

5.2 题解示例

总结

一、Leecode121.买卖股票的最佳时机

题目描述：        

        给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。

输入样例：

        [7,1,5,3,6,4]

输出样例：

        5

1.1 题目分析

        对于股票问题我们在每一天中都会有两种状态：持有股票和不持有股票。这里的持有既包括当天买入，自然也包括之前的几天买入；同理这里的不持有股票其实其实也包括当天卖出股票和前几天卖出了股票。对于动态规划的题目我们一般需要先确定dp数组的含义。因为这里其实包含持有和不持有两种状态，所以本类型的题目我们采用一个二维滚动数组来作为dp数组。

dp数组的含义

  • dp[i][0]：第i天持有股票所得到的最大利润
  • dp[i][1]：第i天不持有该股票所得到的最大利润

dp数组推导式

根据前面的分析，由于在本题中股票其实只能买卖一次，因此在未买入股票的时候所得的利润均为0且在买入股票的瞬间利润会变成-prices[i]，弄清这一点后我们可以比较清晰地获得dp递推式：

  1. dp[i][0] = max(-prices[i]，dp[i-1][0]);
  2. //第i天持有股票其实可以由两个状态推导出来：第i天买入股票-price[i];第i-1天持有股票：dp[i-1][0]
  3.  
  4. dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]);
  5. //第i天不持有股票其实可以由两个状态推导出来：第i天卖出股票dp[i-1][0]+prices[i];第i-1天不持有股票：dp[i-1][1]

确定初始化条件和遍历顺序

        遍历顺序其实很好理解，就是将股票按价值数组进行前序遍历。由于我们求的是在这几天中买卖一次股票所得到的最大利润，因此我们可以先把dp[0][0]初始化为-prices[0]；dp[0][1] = 0。最后需要注意的是我们要求的其实是在最后一天的时候买卖股票的最大利润，所以应该返回dp[prices.size()-1][1]

1.2 题解示例

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         //只能买一次股票
  5.         // 动态规划的解法
  6.         //dp[i][0]:第i天持有股票所得的最多现金；dp[i][1]不持有这只股票
  7.         if(prices.size() == 0) return 0;
  8.         vector<vector<int>> dp(prices.size(),vector<int>(2));
  9.         dp[0][0] -= prices[0];
  10.         dp[0][1] = 0;
  11.         for(int i=1;i<prices.size();i++){
  12.             dp[i][0] = max(dp[i-1][0],-prices[i]);
  13.             dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]);
  14.         }
  15.         return dp[prices.size()-1][1];
  16.     }
  17. };
  18.  
  19. //贪心解法
  20. // class Solution {
  21. // public:
  22. //     int maxProfit(vector<int>& prices) {
  23. //         int low = INT_MAX;
  24. //         int result = 0;
  25. //         for(int i=0;i<prices.size();i++){
  26. //             low = min(low,prices[i]);
  27. //             result = max(result,prices[i]-low);
  28. //         }
  29. //         return result;
  30. //     }
  31. // };

当然了这道题目也可以使用贪心或者回溯算法来求解，这里就不一一赘述了。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、Leecode122.买卖股票的最佳实际II

题目描述：

        给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回 你能获得的最大利润 。

输入样例：

        prices = [7,1,5,3,6,4]

输出样例：

        7

2.1 题目分析

        这道题目对比股票问题I的区别就在于上面的股票问题I是在给出股票天数价值数组的情况下你只能买卖一次股票，但这道题目则是可以多次买卖股票。同样的解题思路我们依旧使用一个二维数组来负责记录我们在这几天内持有股票的情况。dp数组的含义依旧不变，0代表持有，1代表不持有，接着我们按照动态规划的解题步骤来分析一下题目：

dp数组的含义

  • dp[i][0]：第i天持有股票所得到的最大利润
  • dp[i][1]：第i天不持有该股票所得到的最大利润

dp数组推导式

根据前面的分析，由于在本题中股票能买卖多次，因此在每次买入股票的时候都需要加上前一个状态所得到的利润dp[i-1][1]，弄清这一点后我们可以比较清晰地获得dp递推式：

  1. //当天买入和前一个状态便持有的最大值，需要注意但他买入的时候需要加上前一次状态所得最大利润
  2. dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0]);
  3.  
  4. //当天卖出和前一个状态便不持有的利润最大值
  5. dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]);

确定初始化条件和遍历顺序

        初始化的步骤跟只买卖一次股票是一样的。遍历顺序其实很好理解，就是将股票按价值数组进行前序遍历。由于我们求的是在这几天中买卖一次股票所得到的最大利润，因此我们可以先把dp[0][0]初始化为-prices[0]；dp[0][1] = 0。最后需要注意的是我们要求的其实是在最后一天的时候买卖股票的最大利润，所以应该返回dp[prices.size()-1][1]。

2.2 题解示例

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         //相比于买卖股票问题I来说本题的股票可以多次买卖
  5.         //dp[i][0]：
  6.         //dp[i][1]：
  7.         //dp递推式：
  8.         //   dp[i][0]=dp[i-1][1]-prices[i]
  9.         //   dp[i][1]=dp[i-1][0]+prices[i]
  10.         if(prices.size()==0) return 0;
  11.         vector<vector<int>> dp(prices.size(),vector<int>(2,0));
  12.         dp[0][0] -= prices[0];
  13.         dp[0][1] = 0;
  14.         for(int i=1;i<prices.size();i++){
  15.             dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0]);
  16.             dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]);
  17.         }
  18.         return dp[prices.size()-1][1];
  19.     }
  20. };
  21.  
  22. //贪心解法
  23. // class Solution {
  24. // public:
  25. //     int maxProfit(vector<int>& prices) {
  26. //         int result = 0;
  27. //         for (int i = 1; i < prices.size(); i++) {
  28. //             result += max(prices[i] - prices[i - 1], 0);
  29. //         }
  30. //         return result;
  31. //     }
  32. // };

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

三、Leecode123.买卖股票的最佳时机III

题目描述：

        给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

输入样例：

        这道题目在Leecode上的难度被划分为困难

输出样例：

        6

3.1 题目分析

        这道题目在Leecode上的难度被划分为困难，这是题目要求股票在这段时间内只能买卖两次，那么就会有四个状态：第一次持有、第一次不持有、第二次持有、第二次不持有。分清楚状态之后需要确定dp数组的含义以及相应的dp推导式，荔枝个人感觉其实难度没有那么大，后面的股票问题IV和冷冻期会更难一点。

dp数组的含义

  • dp[i][1]：第i天持有股票所得到的最大利润
  • dp[i][2]：第i天不持有该股票所得到的最大利润
  • dp[i][3]：第i天第二次持有股票所得到的最大利润
  • dp[i][4]：第i天第二次不持有该股票所得到的最大利润

dp数组推导式

根据前面的分析，由于在本题中股票仅能买卖两次，因此在每次买入股票的时候都需要加上前一个状态所得到的利润dp[i-1][1]，其实第一次买入股票的时候我们可以等价为前一个状态的利润为0，弄清这一点后我们可以比较清晰地获得dp递推式：

  1. //第一次持有
  2. dp[i][1] = max(0-prices[i],dp[i-1][1]);
  3. //第一次不持有
  4. dp[i][2] = max(dp[i-1][1]+prices[i],dp[i-1][2]);
  5. //第二次持有
  6. dp[i][3] = max(dp[i-1][2]+prices[i],dp[i-1][3]);
  7. //第二次不持有
  8. dp[i][4] = max(dp[i-1][3]+prices[i],dp[i-1][4]);

确定初始化条件和遍历顺序

        遍历顺序跟只前面的股票问题是一样的。其实很好理解，就是将股票按价值数组进行前序遍历。由于我们求的是在这几天中买卖两次股票所得到的最大利润，因此我们可以先把dp[0][0]和dp[0][3]初始化为-prices[0]；dp数组剩下的都初始化为0。最后需要注意的是我们要求的其实是在最后一天的时候买卖股票的最大利润，所以应该返回dp[prices.size()-1][4]。

3.2 题解示例

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         //设置五个状态，也可以是四个状态，主要时区分两次股票的购买情况
  5.         if(prices.size()==0) return 0;
  6.         vector<vector<int>> dp(prices.size(),vector<int>(5,0));
  7.         dp[0][1] -= prices[0];
  8.         dp[0][3] -= prices[0];
  9.         for(int i=1;i<prices.size();i++){
  10.             dp[i][1] = max(dp[i-1][1],0-prices[i]);
  11.             dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]);
  12.             dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i]);
  13.             dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i]);
  14.         }
  15.         return dp[prices.size()-1][4];
  16.     }
  17. };

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

四、买卖股票的最佳时机IV

题目描述：

        给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

输入示例：

        k = 2, prices = [2,4,1]

输出示例：

        2

4.1 题目分析

        前面我们刷了买卖股票最佳时机III，再看这道题目其实感觉是不是很熟悉呢？是的，如果我们将k的值取2其实就变成了买卖股票最佳时机III。因此我们的解题思路应该是基于买卖股票最佳时机III来做出改变的。在前面的两次买卖股票的过程中我们其实设置了四个状态，那么这时候k次买卖的话我们是不是就需要2k个状态，因此我们需要再加一层for循环来遍历所有的持有和不持有状态。首先我们还是根据动态规划的解题步骤来做：

dp数组的含义

  • dp[i][j+1]：第j次持有股票获得的最大利润
  • dp[i][j+2]：第j次不持有股票获得的最大利润

dp数组的推导式

  1. //我们需要明确的是每次买卖股票都具有两次状态,可以类比于上一题来推出
  2. for (int j = 0; j < 2 * k - 1; j += 2) {
  3.     dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
  4.     dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
  5. }

确定初始化条件和遍历顺序

我们知道第0天的买入初始值为-prices[0]，因此不管第0天买卖股票多少次都应该在买入股票的时候初始化为-prices[0]，所以在第0天的时候只要对于下标为奇数我们的初始化应该是这样滴。

  1. for (int j = 1; j < 2 * k; j += 2) {
  2.     dp[0][j] = -prices[0];
  3. }

4.2 题解示例

  1. class Solution {
  2. public:
  3.     int maxProfit(int k, vector<int>& prices) {
  4.         if (prices.size() == 0) return 0;
  5.         vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
  6.         for (int j = 1; j < 2 * k; j += 2) {
  7.             dp[0][j] = -prices[0];
  8.         }
  9.         for (int i = 1;i < prices.size(); i++) {
  10.             for (int j = 0; j < 2 * k - 1; j += 2) {
  11.                 dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
  12.                 dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
  13.             }
  14.         }
  15.         return dp[prices.size() - 1][2 * k];
  16.     }
  17. };
  18. //这道题目其实就是123股票买卖问题的一个变式，也就是将123题目的2次购买股票改为k次，其余的逻辑基本不变

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

五、 Leecode309.最佳买卖股票时机含冷冻期

题目描述： 

        给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输出示例：

         prices = [1,2,3,0,2]

输入示例：

        3

5.1 题目分析

        含有冷冻期的股票问题荔枝个人感觉应该是最难的股票问题了吧，不知道Leecode官网为啥划分为中等难度哈哈哈。这道题目的求解必须要想清楚四个状态：持有股票、不持有股票、在冷冻期间(前一天卖出)和当天卖出。依旧按照老方法来分析这道经典动态规划的题目。

确定dp数组的含义

  • dp[i][0]：第i天持有股票的最大利润
  • dp[i][1]：第i天不持有股票的最大利润(至少是两天前卖出)
  • dp[i][2]：第i天卖出股票获得的最大利润
  • dp[i][3]：第i天处于冷冻期的最大利润

dp数组的推导式

根据前面的四个状态和上面题目积累下来的经验分析，荔枝就直接给出dp数组的推导式了哈，不清楚的留言给荔枝哈。这里要注意冷冻期只有在卖出股票的时候才会有，买入是不会有的哈。

  1. //持有股票的状态，这里由三种情况可以推导出来
  2. //前一天就持有当天没卖出、冷冻期后买入、当天买入
  3. dp[i][0] = max(dp[i-1][0],max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
  4.  
  5. //不持有股票状态主要由两种状态推导出来
  6. //前一天是冷冻期、前一天不持有
  7. dp[i][1] = max(dp[i-1][3],dp[i-1][1]);
  8.  
  9. //卖出股票
  10. dp[i][2] = dp[i-1][0] + prices[i];
  11.  
  12. //冷冻期
  13. dp[i][3] = dp[i-1][2];

确定初始化条件和遍历顺序

dp[0][0]：第0天就持有股票是需要将股票的买入价值给减去的，所以初始化为dp[0][0] = -prices[0]，其余的dp数组的值就初始化为0。遍历顺序依旧是正序遍历。需要注意的是返回值应该取的是冷冻期、卖出股票和不持有股票三者中的最大利润。

5.2 题解示例

  1. class Solution {
  2. public:
  3.     //这道题目主要有四种状态
  4.     //0：持有股票
  5.     //1：保持卖出股票，即两天前就迈出了股票
  6.     //2：今天卖出
  7.     //3：昨天卖出，今天是冷冻期
  8.     int maxProfit(vector<int>& prices) {
  9.         if(prices.size()==0) return 0;
  10.         vector<vector<int>> dp(prices.size(),vector<int>(4,0));
  11.         dp[0][0] = 0-prices[0]; 
  12.         for(int i=1;i<prices.size();i++){
  13.             dp[i][0] = max(dp[i-1][0],max(dp[i-1][3]-prices[i],dp[i-1][1]-prices[i]));
  14.             dp[i][1] = max(dp[i-1][3],dp[i-1][1]);
  15.             dp[i][2] = dp[i-1][0] + prices[i];
  16.             dp[i][3] = dp[i-1][2];
  17.         }
  18.         return max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));
  19.     }
  20. };

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

        这里Leecode上其实还有一道题目是714.买卖股票的最佳时机含手续费 ，这道题目是买卖股票问题II的一个变式，只是加上了手续费其余的思路不变，这里荔枝就不再赘述了，有兴趣的小伙伴可以取刷一刷体会一下。最后总结一下下荔枝对于买卖股票系列问题的看法吧！其实相对来说买卖股票系列问题并没有比背包问题难，而且只要你抓住了定义dp数组的定义其实掌握起来很快，所有的状态和初始化都来自于题目要求和dp数组的定义方式。难度较大的可能是加入冷冻期的问题会比较难想到状态吧哈哈哈哈。总结到现在其实我们发现动态规划的各个系列问题都有其内在的规律和思维，但解题步骤总是不变的，只要能够一步步按照解题步骤分析整道题目其实我们可以发现做起来更有方向性一点。

总结

        在这篇文章中，荔枝主要梳理了有关动态规划的经典问题——股票投资系列问题的例题和解题思路，也相应给出了题解示例。荔枝在最后也对动态规划系列问题做出了自己的体会和总结，有需要的小伙伴们可以跟着荔枝的思路捋上一遍体会一下。算法很难，学好更难，一起加油吧哈哈哈~~~

今朝已然成为过去，明日依然向往未来！我是小荔枝，在技术成长的路上与你相伴，码文不易，麻烦举起小爪爪点个赞吧哈哈哈~~~ 比心心♥~~~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/693550
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号