Compartilhamento de tecnologia

[Coleção de perguntas erradas - Perguntas de programação] O melhor momento para comprar e vender ações (4) (Programação Dinâmica)

2024-07-12

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

Link para a pergunta correspondente:188. O melhor momento para comprar e vender ações IV - LeetCode

Link do tópico correspondente de Niuke:O melhor momento para comprar e vender ações (4)_Niuke Topic_Niuke.com (nowcoder.com)

1. Analise o tema

1、Representação de status

Para distinguir mais claramentecomprarevender, substituímos porTenha açõesesem estoqueDois estados.

  • f[i][j] significa: Não. eu No final do dia, está feito eu transação, atualmente emTenha açõesO benefício máximo do estado.
  • g[i][j] significa: Não. eu No final do dia, está feito eu transação, atualmente emsem estoqueO benefício máximo do estado.

2. Equação de transição de estado

para e[eu j], há também duas situações em que o eu Depois que o dia terminar, complete eu Uma transação em andamento neste momentoTenha açõesstatus:

  • existir i-1 No céu, nas mãosTenha açõese negociado eu Segunda categoria. No i-ésimo dia, não faça nada.A renda neste momento é f[i - 1][j]。
  • existir i-1 No céu, nas mãossem açõese negociado eu Segunda categoria.Em primeiroeu Quando o sol se pôs, comprei ações bilhete.Entãoeu No final das contas, existem ações.A renda neste momento ég[i - 1][j] - preços[i]。

Nos dois casos acima, o que precisamos évalor máximo, então a equação de transição de estado de f é:

f[i][j] = max(f[i - 1][j], g[i - 1][j] - preços[i]

para g[eu j], temos as duas situações a seguir onde podemos eu Depois que o dia terminar, complete eu Uma transação em andamento neste momentosem açõesstatus:

  • existir i-1 No dia do dia, eu não tinha ações em mãos e negociei. eu Segunda categoria.No i-ésimo dia, não faça nada .A renda neste momento ég[i - 1][j]。
  • existir i-1 No dia do dia, eu tinha ações em mãos e as negociava. j - 1 Segunda categoria.Em primeiroeu Quando estiver ensolarado, coloque O estoque foi vendido.Entãoeu No final do dia, negociamos eu Segunda categoria.A renda neste momento é f[i - 1][j - 1] + preços[i]。

Nos dois casos acima, o que precisamos évalor máximo,portanto g A equação de transição de estado é:

g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + preços[i])

A relação comercial entre eles é a seguinte:

3. Inicialização

Porque é necessário eu=0 O estado atual, para que possamos inicializar a primeira linha.
  • quando no 0 dias, só pode estar emComprei uma vezestado, a renda neste momento é -preços[0] ,porqueesse f[0][0] = - preços[0] 。
  • para levar máx. Quando, alguns estados inexistentesSem interferênciafunção, inicializamos todos eles como -INF(usarINT_MIN Durante o processo de cálculo haverátransbordarO risco aqui INF Pegue metade 0x3f3f3f3f , pequeno o suficiente).

4、Ordem de preenchimento do formulário

Preencha cada linha de cima para baixo, cada linha da esquerda para a direita e preencha as duas tabelas juntas.

5、valor de retorno

Retorna o valor máximo no estado de venda, mas não sabemos quantas vezes foi negociado, então retorna g O valor máximo na última linha da tabela.

6、otimização

Nosso número de transações não excederá metade do número total de dias, então podemos primeiro o Vamos lidar com isso e otimizar o tamanho do problema:k = min(k, n / 2)。

2. Código

  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. Reflexão e melhoria

Uma série de questões como comprar e vender ações requer uma familiaridade completa com os principais pontos de conhecimento.

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência