[Sammlung falscher Fragen – Programmierfragen] Der beste Zeitpunkt zum Kauf und Verkauf von Aktien (4) (Dynamische Programmierung)

2024-07-12

Link zur entsprechenden Frage:188. Der beste Zeitpunkt zum Kauf und Verkauf von Aktien IV – LeetCode

Niukes entsprechender Themenlink:Der beste Zeitpunkt zum Kauf und Verkauf von Aktien (4)_Niuke Topic_Niuke.com (nowcoder.com)

1. Analysieren Sie das Thema

1、Statusdarstellung

Zur besseren UnterscheidungkaufenUndverkaufen, wir ersetzen es durchVorräte habenUndkein BestandZwei Staaten.

f[i][j] bedeutet: NEIN. ich Am Ende des Tages ist es geschafft J Transaktion, derzeit inVorräte habenDer maximale Nutzen des Staates.
g[i][j] bedeutet: NEIN. ich Am Ende des Tages ist es geschafft J Transaktion, derzeit inkein BestandDer maximale Nutzen des Staates.

2. Zustandsübergangsgleichung

für F[ich][j], es gibt auch zwei Situationen, in denen die ich Wenn der Tag vorbei ist, ist alles fertig J Derzeit läuft eine TransaktionVorräte habenStatus:

existieren ich-1 Am Himmel, in den HändenVorräte haben, und gehandelt J Zweitklassig. Tun Sie am i-ten Tag nichts.Das Einkommen beträgt zu diesem Zeitpunkt f[ich - 1][j]。
existieren ich-1 Am Himmel, in den Händenkeine Vorräte, und gehandelt J Zweitklassig.In der erstenich Als die Sonne unterging, kaufte ich Aktien Fahrkarte.Alsoich Letzten Endes gibt es Aktien.Das Einkommen beträgt zu diesem Zeitpunktg[i - 1][j] - Preise[i]。

In den beiden oben genannten Fällen benötigen wir FolgendesMaximalwert, also lautet die Zustandsübergangsgleichung von f:

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

für G[ich][j], wir haben die folgenden zwei Situationen, in denen wir können ich Wenn der Tag vorbei ist, ist alles fertig J Derzeit läuft eine Transaktionkeine VorräteStatus:

existieren ich-1 An dem Tag hatte ich keine Aktien in der Hand und habe sie gehandelt. J Zweitklassig.Tun Sie am i-ten Tag nichts .Das Einkommen beträgt zu diesem Zeitpunktg[ich - 1][j]。
existieren ich-1 An dem Tag des Tages hatte ich Aktien in meinen Händen und handelte sie. j - 1 Zweitklassig.In der erstenich Wenn es sonnig ist, stellen Sie es auf Die Aktie wurde verkauft.Alsoich Am Ende des Tages handeln wir J Zweitklassig.Das Einkommen beträgt zu diesem Zeitpunkt f[ich - 1][j - 1] + Preise[i]。

In den beiden oben genannten Fällen benötigen wir FolgendesMaximalwert,daher G Die Zustandsübergangsgleichung von lautet:

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

Die Handelsbeziehung zwischen ihnen ist wie folgt:

3. Initialisierung

Weil es nötig ist ich = 0 Der aktuelle Status, damit wir die erste Zeile initialisieren können.

wenn in der 0 Tage, kann nur in seinEinmal gekauftStaat, das Einkommen zu diesem Zeitpunkt ist -Preise[0] ,WeilDas f[0][0] = - Preise[0] 。
um zu nehmen max Wann, einige nicht existierende ZuständeKeine EinmischungFunktion, wir initialisieren sie alle als -INF(verwendenINT_MIN Während des Berechnungsprozesses wird dies der Fall seinÜberlaufDas Risiko hier INF Nimm die Hälfte 0x3f3f3f3f , klein genug).

4、Reihenfolge des Ausfüllens des Formulars

Füllen Sie jede Zeile von oben nach unten, jede Zeile von links nach rechts und beide Tabellen zusammen aus.

5、Rückgabewert

Gibt den Maximalwert im Verkaufszustand zurück, aber wir wissen nicht, wie oft er gehandelt wurde, also wird er zurückgegeben G Der Maximalwert in der letzten Zeile der Tabelle.

6、Optimierung

Unsere Anzahl an Transaktionen wird die Hälfte der gesamten Anzahl an Tagen nicht überschreiten, also können wir zunächst k Lassen Sie uns damit umgehen und die Größe des Problems optimieren:k = min(k, n / 2)。

2. Code


//力扣
//【动态规划-二维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. Reflexion und Verbesserung

Eine Reihe von Fragen wie der Kauf und Verkauf von Aktien erfordern eine gründliche Vertrautheit mit den Kernwissenspunkten.

Technologieaustausch