这几道题目很相似，把它们放在一起做个比较。
题目大意:从一个\(m \times n\)的格子上左上角走到右下角，只能向右或者向下走，总共有多少种不同的走法？
1. 记忆化递归
这里的递归指的是函数自己调用自己。比如下面递归的办法中，函数dp自己会调用dp。
记忆化指的是把前面已经求解过的值记录在记忆体里面，这样后面要时候的时候就不需要重复计算。
在位置\((y, x)\)的走法上一行\((y - 1, x)\)和前一列\((y, x - 1)\)的走法的和。用一个记忆体\(f[y][x]\)来记录\((y, x)\)的走法。如果已经求解了，则不需要再求解。这样可以节省时间。考虑到边界会越界，对\(f\)进行padding
class Solution(object):
def uniquePaths(self, m, n):
self.f = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
def dp(m, n):
if m == 0 or n == 0:
return 0
if m == 1 and n == 1:
return 1
if self.f[m][n] > 0:
return self.f[m][n]
left_ans = dp(m, n - 1)
upper_ans = dp(m - 1, n)
self.f[m][n] = left_ans + upper_ans
return self.f[m][n]
return dp(m, n)
2. 递推 / 动态规划
递推(或者叫动态规划)的形式和递归很相似，只是把中间结果保存在数组里面从而避免重复求解。
class Solution(object):
def uniquePaths(self, m, n):
self.f = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
self.f[1][1] = 1
def dp(y, x):
for y in range(1, m + 1):
for x in range(1, n + 1):
if y == 1 and x == 1:
continue
else:
self.f[y][x] = self.f[y - 1][x] + self.f[y][x - 1]
dp(m + 1, n + 1)
return self.f[m][n]