方法一 递归
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { return recursion(cost.length,cost); } private int recursion(int i,int[] cost) { //登上0级或1级的成本为0 if(i<2) return 0; //爬到第i级台阶的总花费 return Math.min(recursion(i-1,cost) + cost[i-1],recursion(i-2,cost)+cost[i-2]); } }
运行超时
5/10 组用例通过 运行时间2001ms 占用内存9816KB
方法二 : 循环
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { int[] dp = new int[cost.length+1]; 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]; } }
通过全部用例 运行时间207ms 占用内存22528KB 结论: 从性能上来 看循环的方式迭代 大大优于 递归的方式迭代 ; 空间占用方面,循环方式稍高 2者的区别在于: a. 循环方式需要一个数组存放每轮迭代的结果,递归方式不需要 b. 循环方式从前向后迭代,每一步都把结果放进中间数组 , 递归方式为从后向前迭代 标签:爬楼梯,递归,迭代,--,花费,int,cost,整型,public From: https://www.cnblogs.com/yanher/p/16838743.html