递归和 dp 解决穷举问题时的关系

一些问题需要穷举时，有时候递归和 dp 是都能解决的，典型的例如力扣 p120，三角形的最小路径和。那么这两者解决问题的思路上面有什么区别和联系呢。

共同点：
1）两者解决问题时，要抓住“状态”和“选择”两个核心。明确了“状态”和“选择”，就容易解题了。
2）带备忘录优化的递归，和 dp 是等价的。递归是归纳法，自顶向下；dp 是演绎法，自底向上（当然dp 也可以自顶向下）。

不同点：
1）递归是穷举所有选择，根据选择更新状态；dp 是穷举所有状态，根据状态做选择。

dp 解题方法论：1）明确状态；2）穷举所有状态；3）根据选择更新状态，完成状态转移框架（即递归公式）。

以 p121股票买卖问题为例，状态有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态。

dp[i][k][0 or 1]
0 <= i <= n-1，n 为天数
1 <= k <= K，K 为最多交易数

此问题共 n × K × 2 种状态，全部穷举就能搞定，伪代码如下，

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

dp 求解时要记住如何解释状态，状态要能翻译成自然语言来理解。例如，dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。

完成了「状态」的穷举，接下来需要思考每种「状态」有哪些「选择」，应该如何更新「状态」。这个过程，就是推导 dp 递推公式的过程。最后别忘了 badcase。这些步骤都完成后，就得到了最终的递推公式了。

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,             选择 sell      )
解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )
解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

// 以下是 badcase
dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。