盟族网站建设,货物运输东莞网站建设,大宗交易平台查询,百度站长工具域名查询动态规划法 一、什么是动态规划二、动态规划的解题步骤三、509. 斐波那契数1、动规五部曲#xff1a; 四、70. 爬楼梯1、动规五部曲#xff1a; 五、746. 使用最小花费爬楼梯1、动规五部曲#xff1a; 一、什么是动态规划
动态规划#xff0c;英文#xff1a;Dynamic Pro… 动态规划法 一、什么是动态规划二、动态规划的解题步骤三、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] * (n1)# 3、初始化数组状态dp[0] 0dp[1] 1# 4、确定遍历顺序for i in range(2, n1):# 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] 1dp[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] 1dp[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] 0dp[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))
