Technology Sharing

[Wrong Question Collection - Programming Question] The best time to buy and sell stocks (Part 4) (Dynamic Programming)

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Link to the corresponding question:188. The best time to buy and sell stocks IV - LeetCode

Niuke corresponding question link:The best time to buy and sell stocks (Part 4)_Niuketiba_Niuke.com (nowcoder.com)


1. Analyze the topic

1、Status indication

To make a clearer distinctionBuy it inandSell, we replaceHave stocksandNo stockTwo states.

  • f[i][j] means: i After the day, it's done j transactions, at this timeHave stocksMaximum benefit of the state.
  • g[i][j] means: i After the day, it's done j transactions, at this timeNo stockMaximum benefit of the state.

2. State transfer equation

for f[i][j]There are also two situations in which i After the day is over, complete j The transaction is now in handHave stocksstatus:

  • exist i-1 Day, handHave stocks, and traded j On the i-th day, do nothing.The profit at this time is f[i - 1][j]
  • exist i-1 Day, handNo stocks, and traded j times. i I bought shares on that day.Tickets. Then i At the end of the day, there are stocks. The profit at this time is g[i - 1][j] - prices[i]

In the above two cases, what we need isMaximum, so the state transfer equation of f is:

f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]

for g[i][j], we have the following two situations in the first i After the day is over, complete j The transaction is now in handNo stocksstatus:

  • exist i-1 Days, no stocks in hand, and traded j On the i-th day, do nothing.The profit at this time is g[i - 1][j]
  • exist i-1 Days ago, I had stocks in my hands and traded them. j - 1 times. i When the day comes,The stock is sold. i At the end of the day, we traded. j times. The profit at this time is f[i - 1][j - 1] + prices[i]

In the above two cases, what we need isMaximum,therefore g The state transfer equation is:

g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])

The transaction relationship between them is as follows:


3. Initialization

Because it is necessary to use i=0 So we just initialize the first line.
  • When in the 0 Days, only inBought onceThe state, the profit at this time is -prices[0] ,becausethis f[0][0] = - prices[0]
  • In order to obtain max When some non-existent statesNo interferenceWe initialize them all to -INF(useINT_MIN In the calculation process, there will beoverflowThe risk here INF Half price 0x3f3f3f3f , small enough).

4、Filling order

Fill in each row from top to bottom, and each row from left to right, filling in both tables together.

5、return value

Returns the maximum value in the sell state, but we don't know how many times it was traded, so we return g The maximum value in the last row of the table.


6、optimization

Our number of transactions will not exceed half of the total number of days, so we can first k Let’s deal with it and optimize the scale of the problem:k = min(k, n / 2)


2. Code

  1. //力扣
  2. //【动态规划-二维dp-2个状态】
  3. class Solution {
  4. //f[i][j]:第i天结束后,完成了j次交易,此时处于“买入”状态下的最大利润
  5. //g[i][j]:第i天结束后,完成了j次交易,此时处于“卖出”状态下的最大利润
  6. private:
  7. const int INF=0x3f3f3f3f;
  8. public:
  9. int maxProfit(int k, vector<int>& prices) {
  10. int n=prices.size();
  11. k=min(k, n/2); //优化:处理最多交易次数
  12. vector<vector<int>> f(n, vector<int>(k+1, -INF));
  13. vector<vector<int>> g(n, vector<int>(k+1, -INF));
  14. f[0][0]=-prices[0], g[0][0]=0;
  15. for(int i=1; i<n; i++)
  16. {
  17. for(int j=0; j<=k; j++)
  18. {
  19. f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);
  20. g[i][j]=g[i-1][j];
  21. if(j>=1) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);
  22. }
  23. }
  24. int res=0;
  25. for(int j=0; j<=k; j++)
  26. res=max(res, g[n-1][j]);
  27. return res;
  28. }
  29. };
  30. //【动态规划-二维dp-2k+1个状态】
  31. class Solution {
  32. //dp[i][0] -- 没有操作
  33. //下面j为奇数:买入;j为偶数:卖出 (j的范围:1~2k-1)
  34. //dp[i][j] -- 第1~k次买入
  35. //dp[i][j+1] -- 第1~k次卖出
  36. public:
  37. int maxProfit(int k, vector<int>& prices) {
  38. int n=prices.size();
  39. vector<vector<int>> dp(n, vector<int>(2*k+1));
  40. for(int j=1; j<2*k; j+=2)
  41. dp[0][j]=-prices[0];
  42. for(int i=1; i<n; i++)
  43. {
  44. for(int j=0; j<2*k; j+=2)
  45. {
  46. dp[i][j+1]=max(dp[i-1][j+1], dp[i-1][j]-prices[i]);
  47. dp[i][j+2]=max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);
  48. }
  49. }
  50. return dp[n-1][2*k];
  51. }
  52. };
  1. //牛客
  2. #include <iostream>
  3. #include <cstring>
  4. using namespace std;
  5. const int INF=0x3f3f3f3f;
  6. const int N=1010, M=110;
  7. int prices[N];
  8. int f[N][M], g[N][M];
  9. //f[i][j]:第i天结束后,完成了j次交易,此时处于“买入”状态下的最大利润
  10. //g[i][j]:第i天结束后,完成了j次交易,此时处于“卖出”状态下的最大利润
  11. int main()
  12. {
  13. int n, k;
  14. cin >> n >> k;
  15. for(int i=0; i<n; i++)
  16. cin >> prices[i];
  17. memset(f, -INF, sizeof(f));
  18. memset(g, -INF, sizeof(g));
  19. int res=0;
  20. f[0][0]=-prices[0], g[0][0]=0;
  21. for(int i=1; i<n; i++)
  22. {
  23. for(int j=0; j<=k; j++)
  24. {
  25. f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);
  26. g[i][j]=g[i-1][j];
  27. if(j>0) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);
  28. res=max(res, g[i][j]);
  29. }
  30. }
  31. cout << res << endl;
  32. return 0;
  33. }
  34. //值得学习的代码
  35. #include <iostream>
  36. using namespace std;
  37. const int N = 1010, M = 110;
  38. int n, k, p[N];
  39. int f[N][M], g[N][M];
  40. int main()
  41. {
  42. cin >> n >> k;
  43. for(int i = 0; i < n; i++) cin >> p[i];
  44. k = min(k, n / 2);
  45. for(int j = 0; j <= k; j++) f[0][j] = g[0][j] = -0x3f3f3f3f;
  46. f[0][0] = -p[0], g[0][0] = 0;
  47. for(int i = 1; i < n; i++)
  48. {
  49. for(int j = 0; j <= k; j++)
  50. {
  51. f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]);
  52. g[i][j] = g[i - 1][j];
  53. if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]);
  54. }
  55. }
  56. int ret = 0;
  57. for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);
  58. cout << ret << endl;
  59. return 0;
  60. }

3. Reflection and Improvement

For a series of questions like buying and selling stocks, you need to thoroughly master the core knowledge points.