1、确定dp数组(dp table)以及下标的含义
2、确定递推公式
3、dp数组如何初始化
4、确定遍历顺序
5、举例推导dp数组
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
# 创建dp数组(一维数组)
dp = [0] * (n + 1)
# 初始化dp数组
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]