重庆网站建设技术支持重庆互联网,建设工业网站,织梦古典网站模板,百度爱采购卖家版app下载算法训练营 day42 动态规划 理论基础 斐波那契数 爬楼梯 使用最小花费爬楼梯
理论基础
动态规划#xff0c;英文#xff1a;Dynamic Programming#xff0c;简称DP#xff0c;如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。
所以动态规划中每一个状…算法训练营 day42 动态规划 理论基础 斐波那契数 爬楼梯 使用最小花费爬楼梯
理论基础
动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的
规是由前一个状态推导出来的而贪心是局部直接选最优的
状态转移公式递推公式是很重要但动规不仅仅只有递推公式。
对于动态规划问题我将拆解为如下五步曲这五步都搞清楚了才能说把动态规划真的掌握了
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
斐波那契数
509. 斐波那契数 - 力扣LeetCode
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。
这里我们要用一个一维dp数组来保存递归的结果 确定dp数组以及下标的含义 dp[i]的定义为第i个数的斐波那契数值是dp[i] 确定递推公式 题目已经把递推公式直接给我们了状态转移方程 dp[i] dp[i - 1] dp[i - 2]; dp数组如何初始化 题目中把如何初始化也直接给我们了 确定遍历顺序 从递归公式dp[i] dp[i - 1] dp[i - 2];中可以看出dp[i]是依赖 dp[i - 1] 和 dp[i - 2]那么遍历的顺序一定是从前到后遍历的 举例推导dp数组
class Solution {public int fib(int n) {if(n1) return n;int[] dp new int[n1];dp[0] 0;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i-1]dp[i-2];}return dp[n];}
}爬楼梯
70. 爬楼梯 - 力扣LeetCode
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
动规五部曲
定义一个一维数组来记录不同楼层的状态 确定dp数组以及下标的含义 dp[i] 爬到第i层楼梯有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数组如何初始化 其实这么争论下去没有意义大部分解释说dp[0]应该为1的理由其实是因为dp[0]1的话在递推的过程中i从2开始遍历本题就能过然后就往结果上靠去解释dp[0] 1。 所以我的原则是不考虑dp[0]如何初始化只初始化dp[1] 1dp[2] 2然后从i 3开始递推这样才符合dp[i]的定义。 确定遍历顺序 从递推公式dp[i] dp[i - 1] dp[i - 2];中可以看出遍历顺序一定是从前向后遍历的 举例推导dp数组
class Solution {public int climbStairs(int n) {if (n2) return n;int[] dp new int[n1];dp[1] 1;dp[2] 2;for (int i 3; i dp.length ; i) {dp[i] dp[i-2]dp[i-1];}return dp[n];}
}使用最小花费爬楼梯
746. 使用最小花费爬楼梯 - 力扣LeetCode
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 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]); dp数组如何初始化 看一下递归公式dp[i]由dp[i - 1]dp[i - 2]推出既然初始化所有的dp[i]是不可能的那么只初始化dp[0]和dp[1]就够了其他的最终都是dp[0]dp[1]推出。 确定遍历顺序 因为是模拟台阶而且dp[i]由dp[i-1]dp[i-2]推出所以是从前到后遍历cost数组就可以了。 举例推导dp数组
class Solution {public int minCostClimbingStairs(int[] cost) {if (cost.length0) return 0;if (cost.length1) return cost[0];int[] dp new int[cost.length1];dp[0] 0;dp[1] 0;for (int i 2; i dp.length; i) {dp[i] Math.min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);}return dp[cost.length];}
}
