प्रौद्योगिकी साझेदारी

[गलतप्रश्नानां संग्रहः - प्रोग्रामिंगप्रश्नाः] स्टॉक् क्रयणविक्रययोः सर्वोत्तमः समयः (4) (Dynamic Programming)

2024-07-12

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

तत्सम्बद्धप्रश्नस्य लिङ्क् : १.188. स्टॉकस्य क्रयणविक्रयस्य सर्वोत्तमः समयः IV - LeetCode

नियुके इत्यस्य तत्सम्बद्धः विषयः लिङ्कः : १.स्टॉक्स् क्रयणविक्रययोः सर्वोत्तमः समयः (4)_Niuke Topic_Niuke.com (nowcoder.com)


1. विषयस्य विश्लेषणं कुरुत

1、स्थितिप्रतिपादन

अधिकं स्पष्टतया भेदं कर्तुंक्रीडातुतथाविक्रयिन्, वयं तस्य स्थाने स्थापयामःस्टॉक्स् भवन्तितथान स्टॉक्राज्यद्वयम् ।

  • च[इ][ज] इत्यर्थः: नहि। अहम्‌ दिनान्ते, कृतं भवति व्यवहारः, सम्प्रतिस्टॉक्स् भवन्तिराज्यस्य अधिकतमः लाभः।
  • ग[इ][ज] इत्यर्थः: नहि। अहम्‌ दिनान्ते, कृतं भवति व्यवहारः, सम्प्रतिन स्टॉक्राज्यस्य अधिकतमः लाभः।

2. राज्य संक्रमण समीकरण

कृते [इ][ज्] २., द्वे अपि परिस्थितौ स्तः येषु द अहम्‌ दिवसस्य समाप्तेः अनन्तरं सम्पूर्णम् एकः व्यवहारः, अस्मिन् समये हस्तेस्टॉक्स् भवन्तिस्थितिः:

  • अस्ति i-1 आकाशे हस्तेस्टॉक्स् भवन्ति, व्यापारं च कृतवान् द्वितीय-श्रेणी। इ-दिने किमपि न कुरु ।अस्मिन् समये आयः अस्ति च[इ - १][ज] ।
  • अस्ति i-1 आकाशे हस्तेन स्टॉक्स्, व्यापारं च कृतवान् द्वितीय-श्रेणी।प्रथमेअहम्‌ यदा सूर्यः पतितः तदा अहं भागं क्रीतवन् आसीत् टिकटम् ।अतःअहम्‌ दिनान्ते स्टॉक्स् भवन्ति ।अस्मिन् समये आयः अस्तिg[i - 1][j] - मूल्यानि[i] .

उपर्युक्तयोः प्रकरणयोः अस्माकं यत् आवश्यकं तत् अस्तिअधिकतमं मूल्यम्, अतः f इत्यस्य अवस्थासंक्रमणसमीकरणम् अस्ति : १.

f[i] [j] = अधिकतम(च[i - 1] [ज], g[i - 1] [ज] - मूल्य[i]

कृते [इ][ज्] २., अस्माकं निम्नलिखितौ परिस्थितौ स्तः यत्र वयं शक्नुमः अहम्‌ दिवसस्य समाप्तेः अनन्तरं सम्पूर्णम् एकः व्यवहारः, अस्मिन् समये हस्तेन स्टॉक्स्स्थितिः:

  • अस्ति i-1 दिने मम हस्ते किमपि स्टॉक् नासीत्, अहं तान् व्यापारितवान् । द्वितीय-श्रेणी।इ-दिने किमपि न कुरु .अस्मिन् समये आयः अस्तिग[इ - १][ज] ।
  • अस्ति i-1 दिने मम हस्तेषु स्टॉक्स् आसीत्, तेषां व्यापारः अपि कृतः । ञ - १ द्वितीय-श्रेणी।प्रथमेअहम्‌ यदा सूर्य्यः भवति तदा स्थापयतु स्टॉकः विक्रीतवान् ।अतःअहम्‌ दिनान्ते वयं व्यापारं कुर्मः द्वितीय-श्रेणी।अस्मिन् समये आयः अस्ति च[इ - १][ज - ९. १] + मूल्यानि[इ] ।

उपर्युक्तयोः प्रकरणयोः अस्माकं यत् आवश्यकं तत् अस्तिअधिकतमं मूल्यम्,अतएव इत्यस्य अवस्थासंक्रमणसमीकरणम् अस्ति : १.

g[i][j] = अधिकतम(g[i - 1][j], f[i - 1][j - 1] + मूल्य[i])

तेषां मध्ये व्यापारसम्बन्धः यथा भवति ।


3. आरम्भीकरणम्

यतः तस्य आवश्यकता अस्ति इ=० वर्तमानस्थितिः, अतः प्रथमपङ्क्तिं आरभुं शक्नुमः ।
  • यदा 0 दिवसाः, केवलं मध्ये एव भवितुम् अर्हन्तिएकवारं क्रीतवान्राज्यं, अस्मिन् समये आयः अस्ति -मूल्यानि[0] . ,यतःअयम्‌ च[०] [०] = - मूल्यानि[०] ।
  • ग्रहणार्थम् अधिकतमम् यदा, केचन अस्तित्वहीनाः अवस्थाःन व्यवधानम्function, वयं तान् सर्वान् - इति आरभामः ।INF(उपयुञ्जताम्‌INT_MIN गणनाप्रक्रियायाः समये भविष्यतिअतिप्रवाहःअत्र जोखिमः INF अर्धं गृहाण 0x3f3f3f3f , पर्याप्तं लघु)।

4、प्रपत्रे पूरणक्रमः

प्रत्येकं पङ्क्तिं उपरि अधः, प्रत्येकं पङ्क्तिं वामतः दक्षिणं यावत् पूरयित्वा, द्वयोः सारणीयोः एकत्र पूरयन्तु ।

5、return value

विक्रयस्थितौ अधिकतमं मूल्यं प्रत्यागच्छति, परन्तु वयं न जानीमः यत् कियत्वारं तस्य व्यापारः अभवत्, अतः इदं प्रत्यागच्छति सारणीयाः अन्तिमपङ्क्तौ अधिकतमं मूल्यम् ।


6、अनुकूलन

अस्माकं व्यवहारसङ्ख्या सम्पूर्णदिनसङ्ख्यायाः अर्धाधिका न भविष्यति, अतः प्रथमं शक्नुमः k तस्य निवारणं कुर्मः समस्यायाः आकारं च अनुकूलितं कुर्मः :क = मिन्(क्, न / २) २.


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. चिन्तनं सुधारः च

स्टॉकक्रयणविक्रयादिप्रश्नानां श्रृङ्खलायां मूलज्ञानबिन्दुभिः सह सम्यक् परिचितता आवश्यकी भवति ।