Обмен технологиями

[Сборник неправильных вопросов - Вопросы по программированию] Лучшее время для покупки и продажи акций (4) (Динамическое программирование)

2024-07-12

한어Русский язык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. Уравнение перехода состояний

для ф[я][дж], существуют также две ситуации, в которых я После того, как день закончится, завершите дж В данный момент транзакция находится в обработкеИметь запасыположение дел:

  • существовать я-1 В небе, в рукахИметь запасыи торговал дж Второсортный. В i-й день ничего не делайте.Доход на данный момент составляет ф[и - 1][дж]。
  • существовать я-1 В небе, в рукахнет акцийи торговал дж Второсортный.Во-первыхя Когда солнце упало, я купил акции билет.Такя В конце концов, есть акции.Доход на данный момент составляетг[i - 1][j] - цены[i]。

В двух приведенных выше случаях нам нужномаксимальное значение, поэтому уравнение перехода состояний f имеет вид:

f[i][j] = max(f[i - 1][j], g[i - 1][j] - цены[i]

для г[я][дж], у нас есть следующие две ситуации, когда мы можем я После того, как день закончится, завершите дж В данный момент транзакция находится в обработкенет акцийположение дел:

  • существовать я-1 В тот день у меня на руках не было акций, и я торговал ими. дж Второсортный.В i-й день ничего не делайте .Доход на данный момент составляетг[я - 1][j]。
  • существовать я-1 На рассвете я держал в руках акции и торговал ими. ж - 1 Второсортный.Во-первыхя Когда будет солнечно, поставь Акции были проданы.Такя В конце дня мы торгуем дж Второсортный.Доход на данный момент составляет ф[я - 1][j - 1] + цены[i]。

В двух приведенных выше случаях нам нужномаксимальное значение,поэтому г Уравнение перехода состояний:

g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + цены[i])

Торговые отношения между ними заключаются в следующем:

3. Инициализация

Потому что это необходимо я=0 Текущее состояние, поэтому мы можем инициализировать первую строку.
  • когда в 0 дней, может быть только черезКупил один разсостоянии, доход в это время составляет -цены[0] ,потому чтоэтот f[0][0] = - цены[0] 。
  • чтобы взять Макс Когда некоторые несуществующие государстваНикаких помехфункцию, мы инициализируем их все как -ИНФ(использоватьINT_MIN В процессе расчета будетпереполнениеРиск здесь ИНФ Возьми половину 0x3f3f3f3f , достаточно мал).

4、Порядок заполнения формы

Заполните каждую строку сверху вниз, каждую строку слева направо и заполните обе таблицы вместе.

5、возвращаемое значение

Возвращает максимальное значение в состоянии продажи, но мы не знаем, сколько раз оно было продано, поэтому оно возвращает г Максимальное значение в последней строке таблицы.

6、оптимизация

Наше количество транзакций не будет превышать половины от всего количества дней, поэтому мы можем сначала к Давайте разберемся с этим и оптимизируем размер проблемы:к = мин(к, n / 2)。

2. Код

  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. Размышления и улучшение

Ряд вопросов, таких как покупка и продажа акций, требует глубокого знания основных знаний.

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта