算法训练营 Day 48 | ● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II

[KoEkko]

121. 买卖股票的最佳时机

这道题动态规划的思路：

股票的状态有：

1. 当天持有股票的状态
2. 当天不持有股票的状态

注意：持有 ≠ 买入，不持有 ≠ 卖出

从现实的角度来说，假如我第一天买入了一支股票，一段时间内只要我不卖出，我就一直保持着持有股票的状态，只要等到某天价格高了我就卖出。
所以：
持有股票分为：1.在当天买入股票；2.保持之前持有股票的状态；
不持有股票分为：1.在当天卖出股票；2.保持之前不持有股票的状态；

所以dp数组是一个二维数组，dp的含义是在第i天的时候，dp[i][0]是持有股票的最大金额， dp[i][1]是不持有股票的最大金额
状态转移方程是： dp[i][0] = Math.max(dp[i-1][0], -price[i]) , dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + price[i])

从状态转移方程来看，依赖 dp[0][0]，dp[0][1] 两个状态进行推导，根据含义，dp[0][0] = -price[0]，dp[0][1] = 0;

结果最后只需要 返回，dp[length - 1][1]，最大值肯定是卖出的情况。

function maxProfit(prices: number[]): number {
  const length = prices.length;
  const dp: number[][] = new Array(length)
    .fill(0)
    .map((i) => new Array(2).fill(0));
  dp[0][1] = 0;
  dp[0][0] = -prices[0];
  for (let i = 1; i < length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
    dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
  }
  return dp[length - 1][1];
}

122.买卖股票的最佳时机II

和上一题的区别是：股票可以多次购买，但同样也是只能持有一只股票的情况；

可以多次购买说明，现金额可以有利润累加起来了，所以跟上一题的区别就是，在买入的时候，需要用当前的现金额减去买入的价格。

function maxProfit(prices: number[]): number {
  const length = prices.length;
  if (length === 0) return 0;
  const dp = new Array(length).fill(0).map((_) => new Array(2).fill(0));
  dp[0][0] = -prices[0];
  for (let i = 1; i < length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
  }
  return dp[length - 1][1];
}

贪心解法：

function maxProfit(prices:number[]):number {
  let result = 0;
  for(let i = 1; i < prices.length; i++) {
    result += Math.max(0, prices[i] - prices[i - 1]);
  }
  return result;
}