Berbagi teknologi

[Kumpulan pertanyaan yang salah - Pertanyaan pemrograman] Waktu terbaik untuk membeli dan menjual saham (4) (Pemrograman Dinamis)

2024-07-12

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

Tautan ke pertanyaan terkait:188. Waktu terbaik untuk membeli dan menjual saham IV - LeetCode

Tautan topik terkait Niuke:Waktu terbaik untuk membeli dan menjual saham (4)_Niuke Topic_Niuke.com (nowcoder.com)

1. Analisis topiknya

1、Representasi status

Agar dapat membedakan dengan lebih jelasmembeliDanmenjual, kami menggantinya denganPunya sahamDantidak ada stokDua negara bagian.

  • f[i][j] artinya: TIDAK. Saya Pada akhirnya, semuanya selesai J transaksi, saat ini masukPunya sahamManfaat sebesar-besarnya bagi negara.
  • g[i][j] artinya: TIDAK. Saya Pada akhirnya, semuanya selesai J transaksi, saat ini masuktidak ada stokManfaat sebesar-besarnya bagi negara.

2. Nyatakan persamaan transisi

untuk F[aku j], ada juga dua situasi di mana Saya Setelah hari itu selesai, selesaikan J Sebuah transaksi, ada di tangan saat iniPunya sahamstatus:

  • ada saya-1 Di langit, di tanganPunya saham, dan diperdagangkan J Kelas dua. Pada hari ke-i, jangan lakukan apa pun.Pendapatan saat ini adalah f[i] adalah singkatan dari [i] - 1 [j]。
  • ada saya-1 Di langit, di tangantidak ada stok, dan diperdagangkan J Kelas dua.Yang pertamaSaya Saat matahari terbenam, saya membeli saham tiket.JadiSaya Pada akhirnya, ada stok.Pendapatan saat ini adalahg[i - 1][j] - harga[i]。

Dalam dua kasus di atas, yang kita butuhkan adalahnilai maksimum, jadi persamaan transisi keadaan f adalah:

f[i][j] = maks(f[i - 1][j], g[i - 1][j] - harga[i]

untuk G[aku j], kami memiliki dua situasi berikut di mana kami bisa Saya Setelah hari itu selesai, selesaikan J Sebuah transaksi, ada di tangan saat initidak ada stokstatus:

  • ada saya-1 Pada hari itu, saya tidak memiliki saham apa pun dan saya memperdagangkannya. J Kelas dua.Pada hari ke-i, jangan lakukan apa pun .Pendapatan saat ini adalahhuruf g[i - 1][j]。
  • ada saya-1 Pada hari itu, saya memiliki saham di tangan saya dan memperdagangkannya. j-1 Kelas dua.Yang pertamaSaya Saat cuaca cerah, taruh Stoknya telah terjual.JadiSaya Pada akhirnya, kami berdagang J Kelas dua.Pendapatan saat ini adalah f[i-1][j-1] adalah 1] + harga[i]。

Dalam dua kasus di atas, yang kita butuhkan adalahnilai maksimum,Karena itu G Persamaan transisi keadaan adalah:

g[i][j] = maks(g[i - 1][j], f[i - 1][j - 1] + harga[i])

Hubungan dagang antara keduanya adalah sebagai berikut:

3. Inisialisasi

Karena itu diperlukan saya=0 Keadaan saat ini, sehingga kita dapat menginisialisasi baris pertama.
  • ketika di 0 hari, hanya bisa masukMembeli sekalinegara, pendapatan saat ini adalah -harga[0] ,Karenaini f[0][0] = - harga[0] 。
  • untuk mengambil maks Kapan, beberapa negara bagian tidak adaTidak ada gangguanfungsi, kami menginisialisasi semuanya sebagai -INF(menggunakanINT_MENIT Selama proses perhitungan akan adameluapRisikonya di sini INF Ambil setengahnya 0x3f3f3f3f , cukup kecil).

4、Urutan pengisian formulir

Isi setiap baris dari atas ke bawah, setiap baris dari kiri ke kanan, dan isi kedua tabel secara bersamaan.

5、nilai kembalian

Mengembalikan nilai maksimum dalam keadaan menjual, tapi kita tidak tahu berapa kali diperdagangkan, sehingga kembali G Nilai maksimum pada baris terakhir tabel.

6、optimasi

Jumlah transaksi kami tidak akan melebihi setengah dari jumlah hari keseluruhan, jadi kami bisa dulu aku Mari kita atasi dan optimalkan ukuran masalahnya:k = min(k, n / 2)。

2. Kode

  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. Refleksi dan perbaikan

Serangkaian pertanyaan seperti membeli dan menjual saham memerlukan pemahaman menyeluruh tentang poin-poin pengetahuan inti.

Profil pribadi

Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. Ia telah memberikan banyak kontribusi di bidang open source stasiun dokumentasi pengembang untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang

informasi kontak saya

Surat