1. 斐波那契数列的第n项
def Fibonacci(self, n):
if n==0: return 0
if n==1: return 1
a, b, c = 0, 1, -1
for i in range(2, n + 1):
c = a + b
a = b
b = c
return c
2. 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
方法：第一步找到适用于该题的状态表示，这里把状态函数设定为f(n)，即跳了n个台阶的跳法总数。
现在需要通过先前的信息推导f(n)，假设青蛙跳了n格，如果它是1跳到n格的，
那么一共f(n-1)种跳法；如果是2跳到n格的，那么一共f(n-2)种跳法，所以一共有f(n-1)+f(n-2)种跳法。
\[f(n)= \begin{cases}
1 & n=1 \\
2 & n=2 \\
f(n-1) + f(n-2) & n>2
\end{cases}
\]
3. Unique Paths
给一个m*n矩阵，从左上角到右下角一共多少条路径，要求只能走右边或者左边
方法：设定状态dp[row][col]为在row行col列的路径数，状态转移方程为
\[dp[row][col] = dp[row-1][col] + dp[row]p[col-1]
\]
def uniquePaths(self, m, n):
dp = [[1 for i in range(m)] for i in range(n)]
for i in range(1, n):
for j in range(1,m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
4. Unique Paths II
在上题基础上加了障碍，下面1是障碍
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
方法：在上题基础上状态转换关系还要考虑障碍情况，直接上代码
def uniquePathsWithObstacles(self, obstacleGrid):
# type obstacleGrid: List[List[int]]
row = len(obstacleGrid)
col = len(obstacleGrid[0])
dp = [[1] * col for i in range(row)]
for i in range(0, row):
for j in range(0, col):
if obstacleGrid[i][j]: # 如果这个点是障碍
dp[i][j] = 0
elif i == 0:
dp[i][j] = dp[i][j-1]
elif j == 0:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
5. Triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
给以上这种三角形，返回从顶到底的元素和最小走法（每次只能走邻近子节点）
比如以上的结果：2 + 3 + 5 + 1 = 11
方法：第一步找到状态，可以设定从三角形某行某列到底部的元素和最小走法的元素和大小为dp[row][i]。
比如从2到底结果状态表示为dp[0][0]，其可以被拆解成 min(从3到底的结果dp[1][0], 从4到底的结果dp[1][1]) + 2
状态转换关系即可确定：
\[dp[row][i] = min(dp[row+1][i], dp[row+1][i+1]) + triagnle[row][i]
\]
6. Minimum Path Sum
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
非负二维数组，找到从左上角到右下角的路径，使得元素和最小
上图这个路径 1→3→1→1→1 元素和最小, 为7
方法：设定状态dp[row][col]表示从左上角走到row行col列元素和最小的路径的元素和大小。
状态转移方程为:（需要剪枝）
\[dp[row][col] = min(dp[row][col-1], dp[row-1][col]) + matrix[row][col]
\]