[Väärien kysymysten kokoelma - Ohjelmointikysymykset] Paras aika ostaa ja myydä osakkeita (4) (Dynaaminen ohjelmointi)

2024-07-12

Linkki vastaavaan kysymykseen:188. Paras aika ostaa ja myydä osakkeita IV - LeetCode

Niuken vastaavan aiheen linkki:Paras aika ostaa ja myydä osakkeita (4)_Niuke Topic_Niuke.com (nowcoder.com)

1. Analysoi aihe

1、Tilan esitys

Erottaakseen selvemminostaajamyydä, korvaamme senVaraa osakkeitajaei varastossaKaksi osavaltiota.

f[i][j] tarkoittaa: Ei. i Päivän päätteeksi se on tehty j kauppa, tällä hetkellä käynnissäVaraa osakkeitaValtion suurin hyöty.
g[i][j] tarkoittaa: Ei. i Päivän päätteeksi se on tehty j kauppa, tällä hetkellä käynnissäei varastossaValtion suurin hyöty.

2. Tilasiirtymäyhtälö

varten f[i][j], on myös kaksi tilannetta, joissa i Kun päivä on ohi, valmis j Kauppa käynnissä tällä hetkelläVaraa osakkeitaTila:

olla olemassa i-1 Taivaalla, käsissäVaraa osakkeita, ja vaihdettiin j Toisen luokan. 1. päivänä älä tee mitään.Tulot tällä hetkellä ovat f[i - 1][j]。
olla olemassa i-1 Taivaalla, käsissäei osakkeita, ja vaihdettiin j Toisen luokan.Ensimmäisessäi Kun aurinko laski, ostin osakkeita lippu.Niini Päivän lopussa on osakkeita.Tulot tällä hetkellä ovatg[i - 1][j] - hinnat[i]。

Kahdessa yllä olevassa tapauksessa tarvitsemmeenimmäisarvo, joten f:n tilasiirtymäyhtälö on:

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

varten g[i][j], meillä on seuraavat kaksi tilannetta, joissa voimme i Kun päivä on ohi, valmis j Kauppa käynnissä tällä hetkelläei osakkeitaTila:

olla olemassa i-1 Päivänä minulla ei ollut osakkeita käsissäni ja vaihdoin niitä. j Toisen luokan.1. päivänä älä tee mitään .Tulot tällä hetkellä ovatg[i - 1][j]。
olla olemassa i-1 Aamunkoittopäivänä minulla oli osakkeita käsissäni ja kävin niillä kauppaa. j - 1 Toisen luokan.Ensimmäisessäi Kun paistaa aurinko, laita Osake myytiin.Niini Päivän päätteeksi käymme kauppaa j Toisen luokan.Tulot tällä hetkellä ovat f[i - 1][j - 1] + hinnat[i]。

Kahdessa yllä olevassa tapauksessa tarvitsemmeenimmäisarvo,siksi g Tilasiirtymäyhtälö on:

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

Niiden välinen kauppasuhde on seuraava:

3. Alustus

Koska sitä tarvitaan i = 0 Nykyinen tila, jotta voimme alustaa ensimmäisen rivin.

kun sisällä 0 päivää, voi olla vain sisäänKerran ostettuvaltion tulot tällä hetkellä ovat -hinnat[0] ,koskaTämä f[0][0] = - hinnat[0] 。
ottaakseen max Milloin, jotkut olemattomat valtiotEi häiriöitä-toiminto, alustamme ne kaikki seuraavasti -INF(käyttääINT_MIN Laskentaprosessin aikana tulee olemaanylivuotoRiski tässä INF Ota puolet 0x3f3f3f3f , tarpeeksi pieni).

4、Lomakkeen täyttöjärjestys

Täytä jokainen rivi ylhäältä alas, jokainen rivi vasemmalta oikealle ja täytä molemmat taulukot yhdessä.

5、palautusarvo

Palauttaa maksimiarvon myyntitilassa, mutta emme tiedä kuinka monta kertaa sillä vaihdettiin, joten se palauttaa g Suurin arvo taulukon viimeisellä rivillä.

6、optimointi

Tapahtumamme määrä ei ylitä puolta koko päivien määrästä, joten voimme ensin k Käsitellään sitä ja optimoidaan ongelman koko:k = min(k, n / 2)。

2. Koodi


//力扣
//【动态规划-二维dp-2个状态】
class Solution {
    //f[i][j]:第i天结束后，完成了j次交易，此时处于“买入”状态下的最大利润
    //g[i][j]:第i天结束后，完成了j次交易，此时处于“卖出”状态下的最大利润
private:
    const int INF=0x3f3f3f3f;
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        k=min(k, n/2); //优化:处理最多交易次数
        vector<vector<int>> f(n, vector<int>(k+1, -INF));
        vector<vector<int>> g(n, vector<int>(k+1, -INF));
        f[0][0]=-prices[0], g[0][0]=0;
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<=k; j++)
            {
                f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);
                g[i][j]=g[i-1][j];
                if(j>=1) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);
            }
        }
        int res=0;
        for(int j=0; j<=k; j++)
            res=max(res, g[n-1][j]);
        return res;
    }
};
 
//【动态规划-二维dp-2k+1个状态】
class Solution {
    //dp[i][0] -- 没有操作
    //下面j为奇数：买入；j为偶数：卖出 (j的范围：1~2k-1)
    //dp[i][j] -- 第1~k次买入
    //dp[i][j+1] -- 第1~k次卖出
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n, vector<int>(2*k+1));
        for(int j=1; j<2*k; j+=2)
            dp[0][j]=-prices[0];
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<2*k; j+=2)
            {
                dp[i][j+1]=max(dp[i-1][j+1], dp[i-1][j]-prices[i]);
                dp[i][j+2]=max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);
            }
        }
        return dp[n-1][2*k];
    }
};


//牛客
#include <iostream>
#include <cstring>
using namespace std;
 
const int INF=0x3f3f3f3f;
const int N=1010, M=110;
int prices[N];
int f[N][M], g[N][M];
//f[i][j]:第i天结束后，完成了j次交易，此时处于“买入”状态下的最大利润
//g[i][j]:第i天结束后，完成了j次交易，此时处于“卖出”状态下的最大利润
 
int main()
{
    int n, k;
    cin >> n >> k;
    for(int i=0; i<n; i++)
        cin >> prices[i];
    memset(f, -INF, sizeof(f));
    memset(g, -INF, sizeof(g));
    int res=0;
    f[0][0]=-prices[0], g[0][0]=0;
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<=k; j++)
        {
            f[i][j]=max(f[i-1][j], g[i-1][j]-prices[i]);
            g[i][j]=g[i-1][j];
            if(j>0) g[i][j]=max(g[i][j], f[i-1][j-1]+prices[i]);
            res=max(res, g[i][j]);
        }
    }
    cout << res << endl;
    return 0;
}
 
//值得学习的代码
#include <iostream>
using namespace std;
 
const int N = 1010, M = 110;
 
int n, k, p[N];
int f[N][M], g[N][M];
 
int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> p[i];
 
    k = min(k, n / 2);
    for(int j = 0; j <= k; j++) f[0][j] = g[0][j] = -0x3f3f3f3f;
    f[0][0] = -p[0], g[0][0] = 0;
 
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            f[i][j] = max(f[i - 1][j], g[i - 1][j] - p[i]);
            g[i][j] = g[i - 1][j];
            if(j >= 1) g[i][j] = max(g[i][j], f[i - 1][j - 1] + p[i]);
        }
    }
 
    int ret = 0;
    for(int j = 0; j <= k; j++) ret = max(ret, g[n - 1][j]);
 
    cout << ret << endl;
 
    return 0;
}

3. Heijastus ja parantaminen

Useat kysymykset, kuten osakkeiden ostaminen ja myyminen, edellyttävät perusteellista perehtymistä ydintietopisteisiin.

Teknologian jakaminen