什么是企业营销型网站,泉州企业网站维护制作,云主题 wordpress,wordpress输出所有页面代码随想录刷题day32丨动态规划理论基础#xff0c;509. 斐波那契数#xff0c; 70. 爬楼梯#xff0c; 746. 使用最小花费爬楼梯
1.动态规划理论基础 动态规划#xff0c;英文#xff1a;Dynamic Programming#xff0c;简称DP#xff0c;如果某一问题有很多重叠子问题…代码随想录刷题day32丨动态规划理论基础509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯
1.动态规划理论基础 动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的 动态规划的解题步骤动规五步曲 确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组 为什么要先确定递推公式然后在考虑初始化呢 因为一些情况是递推公式决定了dp数组要如何初始化 代码出错找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的 做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。 然后再写代码如果代码没通过就打印dp数组看看是不是和自己预先推导的哪里不一样。 如果打印出来和自己预先模拟推导是一样的那么就是自己的递归公式、初始化或者遍历顺序有问题了。 如果和自己预先模拟推导的不一样那么就是代码实现细节有问题。
2.题目
2.1斐波那契数
题目链接509. 斐波那契数 - 力扣LeetCode 视频讲解手把手带你入门动态规划 | LeetCode509.斐波那契数_哔哩哔哩_bilibili 文档讲解https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html 解题思路动态规划 确定dp数组以及下标的含义 dp[i]的定义为第i个数的斐波那契数值是dp[i]确定递推公式 dp[i] dp[i - 1] dp[i - 2]dp数组如何初始化 dp[0] 0;
dp[1] 1;确定遍历顺序 从前到后遍历举例推导dp数组 按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是如下的数列0 1 1 2 3 5 8 13 21 34 55如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是一致的。代码 //dp解法
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {public int fib(int n) {if(n 1){return n;}int[] dp new int[n 1];dp[0] 0;dp[1] 1;for(int i 2;i n;i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}//压缩版dp,只需要维护两个数值就可以了不需要记录整个序列
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {public int fib(int n) {if(n 1){return n;}int a 0;int b 1;int c 0;for(int i 2;i n;i){c a b;a b;b c;}return c;}
}//递归解法
//时间复杂度O(2^n)
//空间复杂度O(n)算上了编程语言中实现递归的系统栈所占空间
class Solution {public int fib(int n) { if(n 1){return n;}return fib(n - 1) fib(n - 2);}
}总结 动规五部曲方法很重要
2.2爬楼梯 题目链接70. 爬楼梯 - 力扣LeetCode 视频讲解带你学透动态规划-爬楼梯对应力扣70.爬楼梯| 动态规划经典入门题目_哔哩哔哩_bilibili 文档讲解https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html 解题思路动态规划 确定dp数组以及下标的含义 dp[i] 爬到第i层楼梯有dp[i]种方法确定递推公式 dp[i] dp[i - 1] dp[i - 2] dp数组如何初始化 dp[1] 1dp[2] 2确定遍历顺序 从前向后遍历举例推导dp数组 举例当n为5的时候dp数组应该是 代码 class Solution {public int climbStairs(int n) {if(n 1){return 1;}int[] dp new int[n 1];dp[1] 1;dp[2] 2;for(int i 3;i n;i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}为什么需要特殊处理 n 1 如果 n 1代码只需要直接返回 1因为到达第 1 阶只有一种方法一步爬到。而当 n 1 时你不应该初始化 dp[2] 2;因为数组中只有 dp[0] 和 dp[1]dp[2] 并不存在试图访问它会引发数组越界。 总结 题目中要求的每次可以爬1或者2个台阶也就是说最终到达n阶台阶有两种方式一个是爬1阶台阶到达对应的是从n-1阶台阶开始那么另一个就是爬2阶台阶到达对应的是从n-2阶台阶开始爬而爬n-1阶和n-2阶台阶的方法有dp【n-1】dp【n-2】个。所以最终爬n阶台阶的方法种类就是dp【n-1】dp【n-2】。其实也对应了卡哥所说的从n-1和n-2阶爬上去探究的是几种走法而不是几步。没有讨论dp[0]应该是什么因为dp[0]在本题没有意义
2.3使用最小花费爬楼梯 题目链接746. 使用最小花费爬楼梯 - 力扣LeetCode 视频讲解动态规划开更了| LeetCode746. 使用最小花费爬楼梯_哔哩哔哩_bilibili 文档讲解https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html 解题思路动态规划 图示 确定dp数组以及下标的含义 dp[i]的定义到达第i台阶所花费的最少体力为dp[i]确定递推公式 可以有两个途径得到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[0] 0;//到达 第 0 个台阶是不花费的但从 第0 个台阶 往上跳的话需要花费 cost[0]。
dp[1] 0;//到达 第 1 个台阶是不花费的但从 第1 个台阶 往上跳的话需要花费 cost[1]。确定遍历顺序 从前到后遍历举例推导dp数组 拿示例2cost [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 来模拟一下dp数组的状态变化如下代码 class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp new int[cost.length 1];// 从下标为 0 或下标为 1 的台阶开始因此支付费用为0dp[0] 0;dp[1] 0;// 计算到达每一层台阶的最小费用for(int i 2;i cost.length;i){dp[i] Math.min(dp[i - 1] cost[i - 1],dp[i - 2] cost[i - 2]);}return dp[cost.length];}
}总结 理解自己定义的dp[i] 至关重要初始化的时候要结合实际情况注意数组越界问题
