搞不懂递铺是啥？一文给你讲清楚所有细节

搞不懂递铺是一文给你讲清楚所有细节。

这玩意儿，我刚开始接触动态规划的时候，也是一头雾水。感觉那些公式和状态转移方程，看得我直犯迷糊。什么“最优子结构”、“重叠子问题”，听着就头疼。不过我琢磨着，总得有个玩意儿能让这堆复杂的问题变简单点？后来才明白，递铺（或者叫动态规划）的核心思想就是“把大问题拆成小问题，从小问题的结果往回推，得出大问题的答案”。

我拿最经典的例子来捋捋这个过程。比如，爬楼梯，问你有N阶楼梯，每次只能爬1步或2步，问总共有多少种爬法？

我直接用暴力递归去试。爬到第N阶，要么是从N-1阶爬一步上来，要么是从N-2阶爬两步上来。爬到N阶的方法数，就是爬到N-1阶的方法数加上爬到N-2阶的方法数。这不就是个递推关系吗？

但是，你算着算着就会发现，像算F(5)的时候，你会重复计算F(3)和F(2)。F(4)算的时候，也得算F(3)和F(2)。这些重复计算，特别浪费时间。

这时候，递铺的“备忘录”或者说“表格”就派上用场了。我决定不重复计算了，我得把算过一次的结果存起来。

我开了一个数组，叫它`dp`数组。这个数组的长度就是楼梯的阶数N+1，为啥是N+1，因为我们习惯从0或者1开始计数。我把第i阶楼梯有多少种爬法，存到`dp[i]`里。

我们先从最简单的开始填表。最基础的：

• 爬到第0阶（起点）：也就1种方法，就是不爬，待在原地。dp[0] = 1。
• 爬到第1阶：只能从0阶爬1步上来。dp[1] = 1。

然后，我开始往后推。怎么到第2阶？

• 爬到第2阶：可以从第1阶爬1步，也可以从第0阶爬2步。
• dp[2] = dp[1] + dp[0] = 1 + 1 = 2。

接着是第3阶：

• 爬到第3阶：可以从第2阶爬1步，也可以从第1阶爬2步。
• dp[3] = dp[2] + dp[1] = 2 + 1 = 3。

你看，我就是一步一步，像砌墙一样，用前面的结果来推导后面的结果。每一步都把结果存在那个`dp`数组里，下次再需要这个结果的时候，直接拿出来用，压根不用重新算。

我把这个过程用代码逻辑捋了一遍：

1. 定义一个数组`dp`，大小是N+1。
2. 初始化边界条件：dp[0] = 1; dp[1] = 1;。
3. 写个循环，从i=2开始一直到N。
4. 在循环里面执行状态转移方程：dp[i] = dp[i-1] + dp[i-2]。
5. 循环结束，结果就在dp[N]里面。

这就是最典型的“自底向上”的递铺写法。它把递归里那些乱七八糟的重复计算都干掉了，效率一下子就上去了。我开始觉得，递铺这玩意儿，就是在找那个不变的、能把前面状态串联起来的规律，然后用空间换时间，把计算过程固化下来。

后面遇到别的复杂问题，比如背包问题、最长公共子序列，我都是套这个思路：

• 第一步：定义状态，也就是我需要记录哪些信息来表示子问题的解。
• 第二步：找到状态转移方程，也就是如何从已知的子问题解推导出当前问题的解。
• 第三步：确定初始状态（边界条件）。

只要把这三步摸清楚了，不管题目怎么变，递铺的框架就搭起来了。我就是这么一点点把那些看起来玄乎的动态规划题都啃下来的。