动态规划算法

动态规划算法：

五步曲：

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]