题解 | #最小花费爬楼梯#

思路：动态规划

1.当前在的i位置，不需要花费，只有向上走的时候才会花钱

2.真正的楼顶，是所有台阶的下一个位置。

3.要么从0位置开始，要么从1位置开始。可以走一步，也可以走两步。

• 状态表示：dp[i] 表示：到达i位置的最小化费。

• 转态转移方程：

  情况1：先到达i-1位置的最小花费dp[i-1],加上i-1位置需要的花费，就i位置的花费

  情况2：或者先到达 i-2的位置的最小花费dp[i-2],加上i-2位置需要的花费，就是i位置的花费

  取两种情况的最小值

• dp[i] = min( dp[i-1]+cost[i-1] ，dp[i-2]+cost[i-2] )

• 填表顺序：从左往右

• 初始化：dp[0] = 0 , dp[1] = 0

• 最终返回dp[n],因为楼顶在最后一个数组位置[n-1]的下一个位置。

代码：

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