기술나눔

[잘못된 질문 모음-프로그래밍 질문] 주식을 사고팔기에 가장 좋은 시기(4) (동적 프로그래밍)

2024-07-12

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

해당 질문에 대한 링크:188. 주식을 사고팔기에 가장 좋은 시기 IV - LeetCode

Niuke의 해당 주제 링크:주식을 사고팔기에 가장 좋은 시기 (4)_Niuke Topic_Niuke.com (nowcoder.com)


1. 주제 분석

1、상태 표현

좀 더 명확하게 구별하기 위해구입하다그리고팔다, 우리는 그것을 다음으로 대체합니다.주식을 가지고 있다그리고재고 없음두 가지 상태.

  • f[i][j]는 다음을 의미합니다.: 아니요. 결국엔 다 끝났어 제이 거래, 현재 진행 중주식을 가지고 있다국가의 최대 이익.
  • g[i][j]는 다음을 의미합니다.: 아니요. 결국엔 다 끝났어 제이 거래, 현재 진행 중재고 없음국가의 최대 이익.

2. 상태 전이 방정식

~을 위한 에프[나][제], 또한 두 가지 상황이 있습니다. 하루가 끝나면 완료 제이 현재 진행중인 거래주식을 가지고 있다상태:

  • 존재하다 아이-1 하늘에, 손에주식을 가지고 있다, 그리고 거래됨 제이 이류. i번째 날에는 아무것도 하지 마세요.이때 수입은 f[i-1][j] 이다.
  • 존재하다 아이-1 하늘에, 손에주식 없음, 그리고 거래됨 제이 이류.처음에는해가 졌을 ​​때 나는 주식을 샀다 티켓.그래서 결국 주식이 있습니다.이때 수입은g[i - 1][j] - 가격[i]

위의 두 가지 경우에 우리에게 필요한 것은최대값이므로 f의 상태 전이 방정식은 다음과 같습니다.

f[i][j] = 최대(f[i - 1][j], g[i - 1][j] - 가격[i]

~을 위한 g[나][제], 다음과 같은 두 가지 상황이 있습니다. 하루가 끝나면 완료 제이 현재 진행중인 거래주식 없음상태:

  • 존재하다 아이-1 당일 손에 주식이 하나도 없어서 매매를 했습니다. 제이 이류.i번째 날에는 아무것도 하지 마세요 .이때 수입은g[i - 1][j]
  • 존재하다 아이-1 당일에는 주식을 손에 쥐고 거래를 했습니다. 제이-1 이류.처음에는날이 좋을 때 놓아두세요 주식이 매도되었습니다.그래서결국 우리는 거래를 해요 제이 이류.이때 수입은 f[i-1][j-] 1] + 가격[i]

위의 두 가지 경우에 우리에게 필요한 것은최대값,그러므로 g 상태 전이 방정식은 다음과 같습니다.

g[i][j] = 최대값(g[i - 1][j], f[i - 1][j - 1] + 가격[i])

이들 간의 거래 관계는 다음과 같습니다.


3. 초기화

필요하기 때문에 나=0 현재 상태이므로 첫 번째 줄을 초기화할 수 있습니다.
  • 언제 0 일에만 있을 수 있습니다.한 번 구입상태, 이때 수입은 -가격[0] ,왜냐하면이것 f[0][0] = - 가격[0]
  • 취하기 위해 최대 존재하지 않는 일부 상태가 있는 경우간섭 없음함수, 우리는 그것들을 모두 다음과 같이 초기화합니다.정보(사용INT_MIN 계산 과정에서과다여기의 위험 정보 절반을 가져 가라. 0x3f3f3f3f , 충분히 작습니다).

4、양식 작성 순서

각 행을 위에서 아래로, 각 행을 왼쪽에서 오른쪽으로 채우고 두 표를 함께 채웁니다.

5、반환 값

매도상태의 최대값을 반환하는데, 몇번 거래되었는지 모르므로 반환합니다. g 테이블 마지막 행의 최대값입니다.


6、최적화

거래 횟수는 전체 일수의 절반을 초과하지 않으므로 먼저 케이 이를 처리하고 문제의 크기를 최적화해 보겠습니다.k = 최소(k, n / 2)


2. 코드

  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. 반성과 개선

주식 사고 파는 것과 같은 일련의 질문에는 핵심 지식 포인트에 대한 철저한 숙지가 필요합니다.