70. 爬楼梯（剑指 Offer 10- II. 青蛙跳台阶问题）
递归（英语：Recursion），是指在函数的定义中使用函数自身的方法。有意义的递归通常会把问题分解成规模缩小的同类子问题，当子问题缩写到寻常的时候，我们可以直接知道它的解。然后通过建立递归函数之间的联系（转移）即可解决原问题。
而记忆化递归，就是用数组或者哈希表记录下递归过程中的计算结果，避免重复计算。
以爬楼梯为例，我们想知道爬 n 阶楼梯的方案数 f(n)，由于每次只能爬 1 阶或 2 阶楼梯，所以其实如果知道爬 n - 1 阶和 n - 2 阶楼梯的方案数 f(n-1) 和 f(n-2)，就能知道爬 n 阶楼梯的方案数 f(n) = f(n-1) + f(n-2)。 式子中最小为 n-2 ，根据题意 n-2 >= 0（也可以严格大于0，区别不大，后面相应修改） ，那么 n >= 2。意味着最后一次递归调用为 f(2) = f(1) + f(0)，边界就是 f(1) = 1，f(0) = 1。
直接递归的代码如下：
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
是会超时的，利用记忆化递归可以减少许多重复运算，顺利通过：
class Solution:
memo = dict()
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
if n in self.memo:
return self.memo[n]
self.memo[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return self.memo[n]
思路不难，只是用一个字典 memo 记录出现过的台阶与对应的方案数，如果有记录的话就不用往下递归了，直接返回结果即可。剑指 Offer 的题目区别只在于结果要对 1000000007 取余数。
509. 斐波那契数（剑指 Offer 10- I. 斐波那契数列）
class Solution:
memo = dict()
def fib(self, n: int) -> int:
if n <= 1:
return n
if n in self.memo:
return self.memo[n]
self.memo[n] = self.fib(n-1) + self.fib(n-2)
return self.memo[n]
求斐波那契数，除了边界，其余代码都是一样的。
1137. 第 N 个泰波那契数
class Solution:
memo = dict()
def tribonacci(self, n: int) -> int:
if n == 0:
return 0
if n == 1 or n == 2:
return 1
if n in self.memo:
return self.memo[n]
self.memo[n] = self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3)
return self.memo[n]
这题求的是泰波那契数，思路基本一样，只是递归公式中最小的是 n-3，所以 n >= 3，最后一次递归是 n =3，若知道 n = 0, 1, 2 的值即可得到 n = 3 的结果，所以递归边界可知。（题目其实给了）
746. 使用最小花费爬楼梯
class Solution:
memo = dict()
def minCostClimbingStairs(self, cost: List[int]) -> int:
if len(cost) == 1:
return 0
if len(cost) == 2:
return min(cost)
if tuple(cost) in self.memo:
return self.memo[tuple(cost)]
self.memo[tuple(cost)] = min(cost[0] + self.minCostClimbingStairs(cost[1:]),
cost[1] + self.minCostClimbingStairs(cost[2:]))
return self.memo[tuple(cost)]
这题注意开始爬楼梯时，爬一个台阶是到 cost[0]，两个台阶是到 cost[1]，而不是 cost[0] 为起点。想要继续使用字典只能用可哈希对象元组，不能用数组。
说完记忆化递归，我们说说动态规划。动态规划（英语：Dynamic programming，简称DP）是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
我们应该留意到，动态规划的核心思路也是通过记忆化避免重复运算，实际上，动态规划中的 dp 数组（状态数组）对应的就是记忆化递归中的 memo 字典。关于动态规划的简单入门，我推荐这篇知乎文章。
总结来说就是三点：定义 dp 数组元素的含义（状态是什么）、找出 dp 数组元素间的关系式（状态转移方程）、找出初始条件。用上面的例题进行说明：
70. 爬楼梯（剑指 Offer 10- II. 青蛙跳台阶问题）
在这题中，我们定义 dp 数组元素 dp[i] 的含义为：爬 i 阶楼梯的方案数。数组元素间的关系，由最开始的分析可知，dp[i] = dp[i-1] + dp[i-2]。最后，初始条件为 dp[0] = dp[1] = 1，代码如下：
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]
需要注意的是，dp 数组长度为 n + 1，是因为下标为 0 到 n 共 n + 1 个数，这样才符合数组元素的含义。
509. 斐波那契数（剑指 Offer 10- I. 斐波那契数列）
class Solution:
def fib(self, n: int) -> int:
if n == 0 or n == 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[-1]
修改下初始条件即可。
1137. 第 N 个泰波那契数
class Solution:
def tribonacci(self, n: int) -> int:
if n == 0:
return 0
if n <= 2:
return 1
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = dp[2] = 1
for i in range(3, n + 1):
dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
return dp[-1]
不同的状态转移方程和初始条件。
746. 使用最小花费爬楼梯
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1)
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
dp[n] = min(dp[n-1], dp[n-2])
return dp[-1]
dp 数组的元素 dp[i] 定义为到达第 i 级台阶时最小的总花费，显然就是到达第 i - 1 级台阶与第 i - 2 级台阶的总花费之间的最小值 min(dp[i-1], dp[i-2]) 再加上第 i 级台阶自身的花费 cost[i]，注意 dp 长度是比 cost 大1的，最后一个元素需要单独求。
62. 不同路径（剑指 Offer II 098. 路径的数目）
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 第一行与剩下的m - 1行
dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
这题可以看作是二维数组版的爬楼梯，思路一样，分三步走即可，学习下初始化 dp 数组的写法。
64. 最小路径和（剑指 Offer II 099. 最小路径之和）
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
二维数组版的最小花费爬楼梯，这里有两点要注意：1、创建二维数组不能用 [[0] * n] * m，因为这是浅拷贝，以这种方式创建的二维数组，里面的三个行列表的内存是指向同一块，不管我们修改哪个行列表，其他两个列表也会跟着改变，正确的写法是 [[0] * n for _ in range(m)]。2、由于此处定义 dp 数组的元素 dp[i][j] 是到这一格的数字总和，所以初始化时第一行和第一列也应该是数字总和（除了第一个元素总和是数字本身）。
