讨论/《初级算法》 - 买卖股票的最佳时机/
《初级算法》 - 买卖股票的最佳时机

我写的假设描述的不准确,有歧义,重新假设如下:

  • dp[i][0] 意为第i 天及之前卖出股票所得最大利润;
  • dp[i][1] 意为第i 天及之前买入的股票的最小花费;

dp[i][0]有两种选择:

  1. 最优解是之前某天卖出,利润更高,选择dp[i - 1][0];
  2. 最优解是今天卖出,利润更高,选择(之前某天买入的股票的最小花费 + 今天卖出所得的利润),即dp[i - 1][1] + prices[i];

dp[i][1]有两种选择:

  1. 最优解是之前某天买入,股票更便宜,选择dp[i - 1][1];
  2. 最优解是今天买入,股票更便宜,由于只能买入一次,今天买入,之前就不存在买入卖出行为,所以选择-prices[i];

你根据上述假设,自己去手动求解一个例题就明白了,动态规划纯靠理解,很难。

1
展开全部 19 讨论