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

[गलतप्रश्नानां संग्रहः - प्रोग्रामिंगप्रश्नाः] स्टॉक् क्रयणविक्रययोः सर्वोत्तमः समयः (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.  
  31. //【动态规划-二维dp-2k+1个状态】
  32. class Solution {
  33.     //dp[i][0] -- 没有操作
  34.     //下面j为奇数：买入；j为偶数：卖出 (j的范围：1~2k-1)
  35.     //dp[i][j] -- 第1~k次买入
  36.     //dp[i][j+1] -- 第1~k次卖出
  37. public:
  38.     int maxProfit(int k, vector<int>& prices) {
  39.         int n=prices.size();
  40.         vector<vector<int>> dp(n, vector<int>(2*k+1));
  41.         for(int j=1; j<2*k; j+=2)
  42.             dp[0][j]=-prices[0];
  43.         for(int i=1; i<n; i++)
  44.         {
  45.             for(int j=0; j<2*k; j+=2)
  46.             {
  47.                 dp[i][j+1]=max(dp[i-1][j+1], dp[i-1][j]-prices[i]);
  48.                 dp[i][j+2]=max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);
  49.             }
  50.         }
  51.         return dp[n-1][2*k];
  52.     }
  53. };
  1. //牛客
  2. #include <iostream>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. const int INF=0x3f3f3f3f;
  7. const int N=1010, M=110;
  8. int prices[N];
  9. int f[N][M], g[N][M];
  10. //f[i][j]:第i天结束后，完成了j次交易，此时处于“买入”状态下的最大利润
  11. //g[i][j]:第i天结束后，完成了j次交易，此时处于“卖出”状态下的最大利润
  12.  
  13. int main()
  14. {
  15.     int n, k;
  16.     cin >> n >> k;
  17.     for(int i=0; i<n; i++)
  18.         cin >> prices[i];
  19.     memset(f, -INF, sizeof(f));
  20.     memset(g, -INF, sizeof(g));
  21.     int res=0;
  22.     f[0][0]=-prices[0], g[0][0]=0;
  23.     for(int i=1; i<n; i++)
  24.     {
  25.         for(int j=0; j<=k; j++)
  26.         {
  27.             f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);
  28.             g[i][j]=g[i-1][j];
  29.             if(j>0) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);
  30.             res=max(res, g[i][j]);
  31.         }
  32.     }
  33.     cout << res << endl;
  34.     return 0;
  35. }
  36.  
  37. //值得学习的代码
  38. #include <iostream>
  39. using namespace std;
  40.  
  41. const int N = 1010, M = 110;
  42.  
  43. int n, k, p[N];
  44. int f[N][M], g[N][M];
  45.  
  46. int main()
  47. {
  48.     cin >> n >> k;
  49.     for(int i = 0; i < n; i++) cin >> p[i];
  50.  
  51.     k = min(k, n / 2);
  52.     for(int j = 0; j <= k; j++) f[0][j] = g[0][j] = -0x3f3f3f3f;
  53.     f[0][0] = -p[0], g[0][0] = 0;
  54.  
  55.     for(int i = 1; i < n; i++)
  56.     {
  57.         for(int j = 0; j <= k; j++)
  58.         {
  59.             f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]);
  60.             g[i][j] = g[i - 1][j];
  61.             if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]);
  62.         }
  63.     }
  64.  
  65.     int ret = 0;
  66.     for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);
  67.  
  68.     cout << ret << endl;
  69.  
  70.     return 0;
  71. }

3. चिन्तनं सुधारः च

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

व्यक्तिगत प्रोफाइल

सः ३० वर्षाणाम् अधिकं कालात् प्रौद्योगिक्याः शोधकार्यं कर्तुं समर्पितः अस्ति, तथा च जावा, लिनक्स, जावास्क्रिप्ट्, php, css इत्यादिषु विविधभाषासु प्रवीणः अस्ति, मुक्तस्रोतक्षेत्रे सः बहु योगदानं कृतवान् अस्ति developer documentation station भविष्ये सन्दर्भार्थं प्रौद्योगिकीविकासे केचन विषयाः साझां कर्तुं सर्वे तत् पश्यन्तु

मम सम्पर्कसूचना

मेल