Knowledge Framework

Appearance

On this page

1. 题解 ​

以下是各题题解，推荐先看问题分析，再看题解。

121. 买卖股票的最佳时机 - 力扣（LeetCode） 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

js
var maxProfit = function(prices) {
	let dp_i_0 = 0
	let dp_i_1 = -prices[0]
	const length = prices.length
	
	for (let i = 1; i < length; i++) {
		const tempDp_i_1 = dp_i_1
		dp_i_1 = Math.max(dp_i_1, - prices[i])
		dp_i_0 = Math.max(tempDp_i_1 + prices[i], dp_i_0)
	}
	return dp_i_0
};

2. 问题分析 ​

  1. 有什么状态

    • i: 天数
    • j: 持有、未持有
    • `k: 当前买入次数
    • dp[i][j][k]: 最大利润

  2. 每个【状态】，可以做什么【选择】使得【状态】改变

    • 目前为【持有】：
      • 从上个状态：持有 -> 无操作 买入次数 k
      • 从上个状态：未持有 -> 买入 买入次数 k - 1
    • 目前为【未持有】：
      • 从上个状态：持有 -> 卖出 买入次数 k
      • 从上个状态：未持有 -> 无操作 买入次数 k

  3. 如何定义 DP table/函数来表现【状态】和【选择】

  4. Base Case 是什么

状态：第 i 天 j 状态下总共 k 次买入机会的最大利润

j 0 未持j有

1 jj有

  

选择：

持有 -> 无操作 -> 持有 持有次数 k

未持有 -> 买入 -> 持有 持有次数 k - 1

  

持有 -> 卖出 -> 未持有 持有次数 k

未持有 -> 无操作 -> 未持有 持有次数 k

  

baseCase:
	dp[i][1][0] = -Infinity, 第 i 天，持有，未交易，不可能有这种情况，由于我们求最值，在此设置最小值，方便取最大值。
	dp[i][1][0] = -prices[i] 第 i 天，持有，交易，利润 -


状态转移：

dp[i][1][k] = Math.max(dp[i - 1][1][k], dp[i - 1][0][k - 1] - prices[i])

dp[i][0][k] = Math.max(dp[i - 1][1][k] + prices[i], dp[i - 1][0][k])

最高利润 dp[i][0][...] = 0

  

当 k = 1

baseCase:
	dp[i][1][0] = -Infinity, 第 i 天，持有，未交易，不可能有这种情况，由于我们求最值，在此设置最小值，方便取最大值。
	dp[i][1][0] = -prices[i] 第 i 天，持有，交易，利润 -
	dp[i][0][0] = 0 第 i 天，未持有，未交易，利润 0

  

dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])

			= Math.max(dp[i - 1][1][1], - prices[i])

dp[i][0][1] = Math.max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][1])

  

可以看出, 状态转移中，k 只会为 1 已经不重要了，忽略 k

dp[i][1] = Math.max(dp[i - 1][1], - prices[i])

dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0])

根据状态表达式，再完善 baseCase:
	dp[0][0] = 0, 第 0 天，未持有 0
	dp[0][1] = -prices[i] 第 0 天，持有，利润 -

3. 结论 ​