动态规划法
- 一、什么是动态规划
- 二、动态规划的解题步骤
- 三、509. 斐波那契数
- 1、动规五部曲:
- 四、70. 爬楼梯
- 1、动规五部曲:
- 五、746. 使用最小花费爬楼梯
- 1、动规五部曲:
一、什么是动态规划
动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的
二、动态规划的解题步骤
对于动态规划问题,我将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!
确定dp数组(dp table)以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
三、509. 斐波那契数
1、动规五部曲:
这里我们要用一个一维dp数组来保存递归的结果
1、确定dp数组以及下标的含义
dp[i]的定义为:第i个数的斐波那契数值是dp[i]
2、确定递推公式
为什么这是一道非常简单的入门题目呢?
因为题目已经把递推公式直接给我们了:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
3、dp数组如何初始化
题目中把如何初始化也直接给我们了,如下:
dp[0] = 0;
dp[1] = 1;
4、确定遍历顺序
从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的
class S509:
def func(self, n):
# 1、创建dp数组,dp[i]:表示第i个数是第i个斐波那契数列
dp = [0] * (n+1)
# 3、初始化数组状态
dp[0] = 0
dp[1] = 1
# 4、确定遍历顺序
for i in range(2, n+1):
# 2、确定递推公式
dp[i] = dp[i - 1] + dp[i - 2]
print(dp)
return dp[n]
r = S509()
n = 4
print(r.func(n))
四、70. 爬楼梯
简单
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
1、动规五部曲:
1、确定dp数组以及下标的含义
dp[i]: 爬到第i层楼梯,有dp[i]种方法
2、确定递推公式
如何可以推出dp[i]呢?
从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来。
首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。
还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!
所以dp[i] = dp[i - 1] + dp[i - 2] 。
在推导dp[i]的时候,一定要时刻想着dp[i]的定义,否则容易跑偏。
这体现出确定dp数组以及下标的含义的重要性!
3、dp数组如何初始化
不考虑dp[0]如何初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推,这样才符合dp[i]的定义。
4、确定遍历顺序
从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的
class S70:
def func(self, n):
if n <= 1:
return n
# 1、创建dp数组,dp[i]:走到i台阶,一共用dp[i]种方法
dp = [0] * (n + 1)
# 3、数组初始化
dp[1] = 1
dp[2] = 2
# 4、确定遍历顺序
for i in range(3, n + 1):
# 2、确定递推公式
dp[i] = dp[i - 1] + dp[i - 2]
print(dp)
return dp[n]
r = S70()
n = 4
print(r.func(n))
五、746. 使用最小花费爬楼梯
简单
给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
1、动规五部曲:
1、确定dp数组以及下标的含义
使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。
dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]。
2、确定递推公式
可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]。
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?
一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3、dp数组如何初始化
看一下递归公式,dp[i]由dp[i - 1],dp[i - 2]推出,既然初始化所有的dp[i]是不可能的,那么只初始化dp[0]和dp[1]就够了,其他的最终都是dp[0]dp[1]推出。
新题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说 到达 第 0 个台阶是不花费的,但从 第0 个台阶 往上跳的话,需要花费 cost[0]。
所以初始化 dp[0] = 0,dp[1] = 0;
4、确定遍历顺序
最后一步,递归公式有了,初始化有了,如何遍历呢?
因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。
class S746:
def func(self, cost):
# 1、创建dp数组,dp[i]:走到楼梯i,需要最小的花费为dp[i]
dp = [0] * (len(cost) + 1)
# 3、初始化数组
dp[0] = 0 # 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
dp[1] = 0 # 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
# 4、确定遍历顺序
for i in range(2, len(cost) + 1):
# 2、递推公式
# 在第i步,可以选择从前一步(i-1)花费体力到达当前步,或者从前两步(i-2)花费体力到达当前步
# 选择其中花费体力较小的路径,加上当前步的花费,更新dp数组
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[len(cost)]
r = S746()
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(r.func(cost))