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

题目描述/链接

分析

 

用数组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]);}

运行