动态规划算法：
五步曲：
1、确定dp数组以及下标i的含义
2、递推公式
3、dp[i]初始化
4、遍历顺序
5、打印dp数组
实例一：斐波那契数列
1 1 2 3 5 8 13 21…n
解题步骤：
确定dp数组以及下标i的含义：
dp[i]数组：第i个下标对应的斐波那契数值
递推公式：
I>=2 => dp[i] = dp[i-1]+dp[i-2]
i< 2 => dp[0] = 1 dp[1]=1
dp[i]初始化：
dp[0] = 1 dp[1]=1
遍历顺序：
从前向后
打印dp数组：
def fib(n):
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
if n < 2:
return dp[n]
for i in range(2,n):
dp[i] = dp[i-1]+dp[i-2]
print(dp[i])
return dp[n]
实例二：最大子序和(找出一个具有最大和的连续子数组)
nums = [-2,1,-3,4,-1,2,1,-5,4]
解题步骤：
确定dp[i]数字以及下标i的含义：
dp[i]数组：包括i之前的连续最大和的值
递推公式：
dp[i] = (nums[I]+dp[i-1],nums[i])
dp[i]初始化：
dp[i] = nums[0]
遍历顺序：
从前向后
打印dp数组
实例三、实例三、爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
dp[i]: 爬i层楼梯的方法数
递推公式：
dp[i] = dp[i-1]+dp[i-2]
dp[i]初始化：
dp[1] = 1
dp[2]= 2
实例四、最小花费爬楼梯
dp[i]：爬到第i层需要的最小花费
递推公式：
dp[I] = min(dp[i-1]+cost[I],dp[i-2]+cost[i])
dp[i]初始化：
dp[0] = cost[0]
dp[1] = min(cost[0]+cost[1],cost[1])=> cost[1]
实例四、最大子序列和：nums = [-2,1,-3,4,-1,2,1,-5,4]
dp[i]: 包括下标i的连续子序列的最大和
递推公式：
dp[i]= max(nums[i],dp[i-1]+nums[i])
dp[i]初始化：
dp[0] = nums[0]
