淄博做网站优化公司,seo工资一般多少,诸暨网站制作哪些公司制作,做ppt的模板网站面试题88#xff1a; 问题#xff1a;
一个数组cost的所有数字都是正数#xff0c;它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本#xff0c;在支付了成本cost[i]之后可以从第i级台阶往上爬1级或2级。请计算爬上该楼梯的最少成本。
解决方案一#xff1a; 问题
一个数组cost的所有数字都是正数它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本在支付了成本cost[i]之后可以从第i级台阶往上爬1级或2级。请计算爬上该楼梯的最少成本。
解决方案一递归力扣超时
解决方案
从第i级台阶往上爬的最少成本应该是从第i-1级台阶往上爬的最少成本和从第i-2级台阶往上爬的最少成本的较小值再加上爬第i级台阶的成本。故该关系的状态转移方程为dpi min(dp(i-1),dp(i-2)) cost[i]。
源代码
class Solution {public int minCostClimbingStairs(int[] cost) {int len cost.length;return Math.min(dfs(cost,len-1),dfs(cost,len-2));}private int dfs(int[] cost,int len){if(len 2){return cost[len]; }return Math.min(dfs(cost,len-1),dfs(cost,len-2)) cost[len];}
}解决方案二使用缓存的递归
解决方案
不使用缓存的话需要反复计算前一个递归。例如求f9就需要先求f8和f7而计算f8就需要计算f7和f6以此类推需要重复计算的数据量太大、时间复杂度很高。故为了避免重复计算带来的问题一个常用的解决办法是将已经求解过的问题的结果保存下来。在每次求解一个问题之前应先检查该问题的求解结果是否已经存在。如果问题的求解结果已经存在则不再重复计算只需要从缓存中读取之前求解的结果。
源代码
class Solution {public int minCostClimbingStairs(int[] cost) {int len cost.length;int[] dp new int[len];dfs(cost,dp,len-1);//dfs(cost,dp,len-2);这条代码是我加上去的不然跑不过样例[1,100]加了还是超时力扣还差两个样例跑不过。dfs(cost,dp,len-2);return Math.min(dp[len-1],dp[len-2]);}private void dfs(int[] cost,int[] dp,int len){if(len 2){dp[len] cost[len];}else if(dp[len] 0){dfs(cost,dp,len-1);dfs(cost,dp,len-2);dp[len] Math.min(dp[len-1],dp[len-2]) cost[len];}}
}解决方案三空间复杂度为On的迭代
解决方案
自下而上地解决这个过程也就是从子问题入手根据两个子问题fi-1和fi-2的解求出fi的结果。
源代码
class Solution {public int minCostClimbingStairs(int[] cost) {int len cost.length;int[] dp new int[len];dp[0] cost[0];dp[1] cost[1];for(int i 2;i len;i){dp[i] Math.min(dp[i-1],dp[i-2]) cost[i];}return Math.min(dp[len-1],dp[len-2]);}
}解决方案四空间复杂度为O1的迭代
解决方案
前面用一个长度为n的数组将所有fi的结果都保存下来。求解fi时只需要fi-1和fi-2的结果从f0到fi-3的结果其实对求解fi并没有任何作用。也就是说在求每个fi的时候需要保存之前的fi-1和fi-2的结果因此只要一个长度为2的数组即可。
源代码
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp new int[]{cost[0],cost[1]};for(int i 2;i cost.length;i){dp[i % 2] Math.min(dp[0],dp[1]) cost[i];}return Math.min(dp[0],dp[1]);}
}
