笔试强训2）最小花费爬楼梯（动态规划-线性dp）

用户11162265

发布于 2024-10-29 08:15:23

7300

代码可运行

文章被收录于专栏：C语言C语言

运行总次数：0

代码可运行

题目描述/链接

分析

用数组dp来存储到i位置的花费，

由题意知，起始位置是在下标0或1的位置，开始爬时不需要费用，

dp[0] = dp[1] = 0

给定数组长度n，需要爬到的楼梯顶部就是下标为n的位置，

到该位置(楼顶)的最小花费是：

从 n-1爬一个位置的花费+ 到n-1位置的花费

dp[n] = cost[n-1] + dp[n-1]

或者是

从n-2爬两个位置的花费+到n-2位置的花费

dp[n] = cost[n-2] + dp[n-2]

因为题上说一次可以爬一个台阶或者两个，所以有两种情况。

所以我们只需要再找出这两种情况中花费最小的情况，就能找到到楼梯顶部的最小花费

代码：

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] cost = new int[n];
        for(int i = 0; i < n; i++){
            cost[i] = in.nextInt();
        }
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for(int i = 2; i < n + 1; i++){
            int dp1 = dp[i - 1] + cost[i - 1];
            int dp2 = dp[i -2] + cost[i - 2];
            dp[i] = Math.min(dp1, dp2);
        }
        System.out.println(dp[n]);
    }

运行