你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
数据范围:数组长度满足 ,数组中的值满足
[2,5,20]
5
你将从下标为1的台阶开始,支付5 ,向上爬两个台阶,到达楼梯顶部。总花费为5
[1,100,1,1,1,90,1,1,80,1]
6
你将从下标为 0 的台阶开始。 1.支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。 2.支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。 3.支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。 4.支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。 5.支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。 6.支付 1 ,向上爬一个台阶,到达楼梯顶部。 总花费为 6 。
public int minCostClimbingStairs (int[] cost) { // write code here int n = cost.length; if(n == 1){ return 0; } else if(n == 2){ return Math.min(cost[0], cost[1]); } else{ int[] a = Arrays.copyOfRange(cost, 0, n-1); int[] b = Arrays.copyOfRange(cost, 0, n-2); int x1 = minCostClimbingStairs(a) + cost[n-1]; int x2 = minCostClimbingStairs(b) + cost[n-2]; return Math.min(x1,x2); } }这么写貌似理论可行但是速度很慢,不知道怎么改进。
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+1;i++){ dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]); } return dp[cost.length]; }
public class Solution { public int minCostClimbingStairs (int[] cost) { // 爬到第i级楼梯所需的最小花销 int[] dp = new int[cost.length + 1]; // 可以选择从0或者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]; } }
import java.util.*; public class Solution { public int minCostClimbingStairs (int[] cost) { int n = cost.length; if (n <= 1) return cost[0]; int a = cost[0], b = cost[1], c = 0; for (int i = 2; i < n; i++) { c = Math.min(a, b) + cost[i]; a = b; b = c; } return Math.min(a, b); } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { //dp[n]=min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2]),爬到第n层的最低花费 //dp[1]=dp[0]+cost[0]/0 //dp[2]=dp[1]+cost[1]/dp[0]+cost[0] int a = 0,b = 0,c = 0; for(int i = 2;i<=cost.length;i++){ c = Math.min(a+cost[i-2],b+cost[i-1]); a = b; b = c; } return c; } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { if(cost.length == 1) return cost[0]; // 初始化两个变量, dp1 = 下标为0的台阶,需要花费, dp2 = 下标为1的台阶,需要花费 int dp1 = cost[0], dp2 = cost[1]; // 遍历cost数组,从下标2开始 for (int i = 2; i < cost.length; i++) { // 暂存dp2,因为dp1和dp2的花费需要向后移动,所以dp1的花费需要切换到 dp2 int temp = dp2; // 将当前i层台阶的花费 + dp1花费, 与 当前i层台阶的花费 + dp2花费 取最小花费值 赋给dp2 // 即当达到下标为i层台阶的时候,花费为 (当前i层台阶的花费 + dp1花费, 与 当前i层台阶的花费 + dp2花费 取最小花费值) dp2 = Math.min(cost[i] + dp1, cost[i] + dp2); // 然后dp1的花费后移,改为之前的dp2 dp1 = temp; } // 循环结束时,对比dp1 和 dp2的花费 取最小值 return dp1 > dp2 ? dp2 : dp1; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { int[] dp = new int[cost.length]; dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < cost.length; i++) { dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } return Math.min(dp[dp.length - 1], dp[dp.length - 2]); } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs(int[] cost) { //方法:要使得f(n)最小则,到达n需要从n-1或者n-2跳过来,则需要取跳到n-1或者n-2的最小花费拿出来 //设n层最小花费f(n),n-1层为f(n-1) n-2层为f(n-2) 而从n-1跳到n的花费为cost[n-1],从n-2跳到n的花费为cost[n-2], //即:f(n) = Math.min(f(n-1)+cost[n-1],f(n-2)+cost[n-1]) f(0)=f(1) = 0 int length = cost.length;//楼层个数 int [] minmoney = new int[length+1];//因为最后一层必须跨过去,所以长度+1 //0位和1位不需要花费,二开始即minmoney[0]=0=minmoney[1],如果长度大于2,则0位和1位默认0 for (int i = 2; i <= length; i++) { minmoney[i] = Math.min(minmoney[i-1]+cost[i-1],minmoney[i-2]+cost[i-2]); } return minmoney[length]; } }
应该挺好理解的,我也不多说什么了。我第一遍写的时候,用的是,递归写的,之后因为超时了,想到要把前面求过的存起来,因为用递归的话,有的值会求很多遍。另外,由于要的结果是顶层的路费。最后到达顶层的时候,是不需要再加路费的,所以我把顶层的那一步留了出来。
public int minCostClimbingStairs (int[] cost) { int[] arr = new int[cost.length]; arr[0] = cost[0]; arr[1] = cost[1]; for(int i = 2;i < arr.length;i++){ arr[i] = Math.min(arr[i-1],arr[i-2])+ cost[i]; } return Math.min(arr[arr.length-1],arr[arr.length-2]); }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { // write code here int[] dp=new int[cost.length+1]; dp[0]=0; dp[1]=cost[0]; for(int i=2;i<dp.length;i++){ dp[i]=cost[i-1]+Math.min(dp[i-1],dp[i-2]); } return Math.min(dp[dp.length-1],dp[dp.length-2]); } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { // write code here int n=cost.length; int[] min_money=new int[n]; min_money[n-1]=cost[n-1]; min_money[n-2]=cost[n-2]; for(int i=n-3;i>=0;i--){ min_money[i]=Math.min(min_money[i+2]+cost[i],min_money[i+1]+cost[i]); } return Math.min(min_money[0],min_money[1]); } }
定义dp[i]表示为跳到第i个台阶的最小花费(第i个台阶的花费不计算在内);
最终,返回值应该为dp[n];
起跳点为0或者1,那么对应的base case为:
dp[0] = 0, dp[1] = 0; // 表示跳到0、1位置需要总花费0的代价;
因为青蛙每次有两种选择,分别为1步和两步,那么dp[i] 有两种可能:
综上,我们要求的是dp[i]表示到达i位置的最小花费,所以 dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型一维数组 * @return int整型 */ public int minCostClimbingStairs (int[] cost) { // dp[i] 表示 跳到i这个台阶的最低花费; int n = cost.length; int[] dp = new int[n+1]; // 返回值 为 dp[n] dp[0] = 0; dp[1] = 0; for (int i = 2; i<= n; i++) { dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]); } return dp[n]; } }```
import java.util.*; public class Solution { public int minCostClimbingStairs (int[] cost) { if(cost==null || cost.length==1) return 0; int n = cost.length; int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 0; for(int i=2; i<=n; i++){ dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]); } return dp[n]; } }