Κοινή χρήση τεχνολογίας

한어Русский язык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. Εξίσωση μετάβασης κατάστασης

Για φά[i][j], υπάρχουν επίσης δύο καταστάσεις στις οποίες το Εγώ Αφού τελειώσει η μέρα, ολοκληρώστε ι Μια συναλλαγή, στο χέρι αυτή τη στιγμήΝα έχετε αποθέματακατάσταση:

• υπάρχει i-1 Στον ουρανό, στα χέριαΝα έχετε αποθέματα, και διαπραγματεύονται ι Δεύτερης διαλογής. Την ιη ημέρα, μην κάνετε τίποτα.Το εισόδημα αυτή τη στιγμή είναι f[i - 1][j]。
• υπάρχει i-1 Στον ουρανό, στα χέριαχωρίς αποθέματα, και διαπραγματεύονται ι Δεύτερης διαλογής.Κατά την πρώτηΕγώ Όταν έπεσε ο ήλιος, αγόρασα μετοχές εισιτήριο.ΈτσιΕγώ Στο τέλος της ημέρας, υπάρχουν αποθέματα.Το εισόδημα αυτή τη στιγμή είναιg[i - 1][j] - τιμές[i]。

Στις δύο παραπάνω περιπτώσεις αυτό που χρειαζόμαστε είναιμέγιστη αξία, άρα η εξίσωση μετάβασης κατάστασης της f είναι:

f[i][j] = max(f[i - 1][j], g[i - 1][j] - τιμές[i]

Για σολ[i][j], έχουμε τις ακόλουθες δύο καταστάσεις όπου μπορούμε Εγώ Αφού τελειώσει η μέρα, ολοκληρώστε ι Μια συναλλαγή, στο χέρι αυτή τη στιγμήχωρίς αποθέματακατάσταση:

• υπάρχει i-1 Την ημέρα της ημέρας, δεν είχα μετοχές στα χέρια μου και τις αντάλλαξα. ι Δεύτερης διαλογής.Την ιη ημέρα, μην κάνετε τίποτα .Το εισόδημα αυτή τη στιγμή είναιg[i - 1][j]。
• υπάρχει i-1 Τα ξημερώματα είχα στα χέρια μου μετοχές και τις διαπραγματεύτηκα. j - 1 Δεύτερης διαλογής.Κατά την πρώτηΕγώ Όταν έχει ήλιο, βάλε Το απόθεμα πουλήθηκε.ΈτσιΕγώ Στο τέλος της ημέρας, κάνουμε εμπόριο ι Δεύτερης διαλογής.Το εισόδημα αυτή τη στιγμή είναι f[i - 1][j - 1] + τιμές[i]。

Στις δύο παραπάνω περιπτώσεις αυτό που χρειαζόμαστε είναιμέγιστη αξία,επομένως σολ Η εξίσωση μετάβασης κατάστασης είναι:

g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + τιμές[i])

Η μεταξύ τους εμπορική σχέση έχει ως εξής:

---

3. Αρχικοποίηση

• όταν στο 0 ημέρες, μπορεί να είναι μόνο μέσαΑγοράστηκε μια φοράκράτος, το εισόδημα αυτή τη στιγμή είναι -τιμές[0] ,επειδήΑυτό f[0][0] = - τιμές[0] 。
• προκειμένου να πάρει Μέγιστη Πότε, κάποιες ανύπαρκτες πολιτείεςΚαμία παρέμβασηλειτουργία, τα αρχικοποιούμε όλα ως -INF(χρήσηINT_MIN Κατά τη διαδικασία υπολογισμού θα υπάρχουνξεχείλισμαΟ κίνδυνος εδώ INF Πάρτε το μισό 0x3f3f3f3f , αρκετά μικρό).

---

4、Σειρά συμπλήρωσης της φόρμας

Συμπληρώστε κάθε σειρά από πάνω προς τα κάτω, κάθε σειρά από αριστερά προς τα δεξιά και συμπληρώστε και τους δύο πίνακες μαζί.

---

5、επιστρεφόμενη τιμή

Επιστρέφει τη μέγιστη αξία στην κατάσταση πώλησης, αλλά δεν γνωρίζουμε πόσες φορές έγινε η διαπραγμάτευση, επομένως επιστρέφει σολ Η μέγιστη τιμή στην τελευταία σειρά του πίνακα.

---

6、βελτιστοποίηση

Ο αριθμός των συναλλαγών μας δεν θα υπερβαίνει το ήμισυ του συνόλου των ημερών, οπότε μπορούμε πρώτα κ Ας το αντιμετωπίσουμε και ας βελτιστοποιήσουμε το μέγεθος του προβλήματος:k = min(k, n / 2)。

---

2. Κωδ

//力扣
//【动态规划-二维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. Προβληματισμός και βελτίωση

Μια σειρά ερωτήσεων όπως η αγορά και η πώληση μετοχών απαιτεί μια πλήρη εξοικείωση με τα βασικά σημεία γνώσης.