解法一
如果到第i
个台阶,我们可以从第i-1
个台阶跳一步
上来,也可以从第i-2
个台阶跳两步
上来。哪个花费少我们就选择从哪个跳上来。我们定义dp[i]
表示到第i
个台阶需要的最小花费,那么我们可以得出递推公式
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
其中
dp[i - 2] + cost[i - 2]
表示从第i-2
个台阶跳到第i
个台阶的最小花费dp[i - 1] + cost[i - 1]
表示从第i-1
个台阶跳到第i
个台阶的最小花费
有了递推公式,我们再来看下代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] cost = new int[in.nextInt()];
for (int i = 0; i < cost.length; i++) {
cost[i] = in.nextInt();
}
System.out.println(minCostClimbingStairs(cost));
}
private static 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 - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[cost.length];
}
}
解法二
上面代码我们还可以优化一下,因为计算当前位置的时候只和他前面的两个位置有关,所以我们可以不需要dp
数组,直接使用几个变量即可,代码如下
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] cost = new int[in.nextInt()];
for (int i = 0; i < cost.length; i++) {
cost[i] = in.nextInt();
}
System.out.println(minCostClimbingStairs(cost));
}
private static int minCostClimbingStairs(int[] cost) {
int first = 0;
int second = 0;
int third = 0;
for (int i = 2; i <= cost.length; i++) {
third = Math.min(first + cost[i - 2], second + cost[i - 1]);
first = second;
second = third;
}
return third;
}
}
我把部分算法题整理成了PDF
文档,截止目前总共有1000多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ 提取码:6666