外国人爱做视频网站吗,服务器买好了怎么搭建自己的网站,企业优化网站,vps正常网站打不开LeetCode 509 斐波那契数列
这题动规五部曲都定义得比较明确。首先是dp数组下标#xff0c;题目中给定F(0) 0说明从0开始#xff0c;dp[i]直接表示F(i)的值即可。递推公式也直接给出了#xff0c;也给了开头两个作为递推基础的数值作为初始化依据。遍历顺序也指明是从前往…LeetCode 509 斐波那契数列
这题动规五部曲都定义得比较明确。首先是dp数组下标题目中给定F(0) 0说明从0开始dp[i]直接表示F(i)的值即可。递推公式也直接给出了也给了开头两个作为递推基础的数值作为初始化依据。遍历顺序也指明是从前往后即由下标从小到大递推。
但是举例推导这一步也是不能省的比如如果n小于等于1那么就不能对dp[1]按照题目条件直接初始化会报错。
最后代码如下
class Solution {public int fib(int n) {if (n 0 || n 1) return n;int[] num new int[n 1];for (int i 0; i n; i) num[i] 0;num[0] 0; num[1] 1;for (int i 2; i n; i) {num[i] num[i - 1] num[i - 2];}return num[n];}
}
LeetCode 70 爬楼梯
这题最后代码写出来很短但其实用动规来写不是很简单。
首先我们要明确为什么要用动规。这题其实可以用回溯也可以用递归。但是回溯更适合记录路径递归需要消耗内存较大。而动规很好地拟合了这道题目同时时间和空间开销都没有前两种方法那么高。
动规本意也就在这里——用循环和递推条件直接解决问题。但是代价就是想的东西要多一些也就是我们要找出子问题到当前问题的推导条件和它们之间的关系比如这题就是两级台阶下的位置到当前位置可以一步到一级台阶下的位置到当前位置可以一步到我们将这两个子问题的方法数加起来就得到了当前问题的解。但是问题来了为什么不让两级前的台阶走两步呢但按照我们对dp数组和下标的定义dp[i]是走到第i级台阶的方法数上面这个问题实际上属于一级前台阶方法数而不属于两级前台阶方法数了。而且用这种视角来思考的话用的就不是动规因为那不是子问题到当前问题的推导而是实际事情发生中的状态。这是动规和平常思路之间最大的差别了。
到这里我们递推公式和dp数组定义和下标含义就都得出来了。接下来初始化方法和遍历顺序是这样我们找出能够和最开始子问题发生关联的最大下标把它在递推公式中的子问题dp值初始化即可。这里我们需要结合实际情况设置dp[0]和dp[1]为1因为能够和最开始一级台阶都没爬的时候的子问题发生关联的最大下标就是2了。遍历顺序从小到大也就是从前往后进行。
举例推导方面和上一题差不多主要就是对比较小的时候的一些特例进行特殊考量。
代码如下
class Solution {public int climbStairs(int n) {if (n 1) return 1;int[] dp new int[n 1];dp[0] 1; dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}
LeetCode 746 使用最小花费爬楼梯
这题其实和上一题很像不过递推逻辑要稍微变一下变成取两级之前台阶从该台阶跳上来开销和一级之前台阶从该台阶跳上来开销中比较小的那个。子问题和当前问题之间关系是一样的。所以dp数组下标和含义基本一致。这题由于加入了开销所以也无法像上一题那样从所有台阶下面开始往上跳初始化时候直接将dp[0]和dp[1]初始化为1即可原因和上一题一样这里不再赘述。
遍历顺序从下往上对应也是从小到大。
代码如下
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp new int[cost.length 1];dp[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];}
}
很简洁但背后思考过程很丰富。
