【Lintcode】1054. Min Cost Climbing Stairs

题目地址：

https://www.lintcode.com/problem/min-cost-climbing-stairs/description

给定一个数组 $A$， $A[i]$表示走到 $i$这个位置所需的花费（题目保证花费非负）。允许从 $i=0$或 $1$开始走，每次可以走 $1$或 $2$步，问若要到达 $A$的末尾再后面一格至少需要多少花费。

思路是动态规划。设 $f[i]$表示要走到 $i$这个位置所需的最小花费。那么 $f[0]=A[0]$， $f[1]=A[1]$，并且 $f[i]=A[i]+\min(f[i-1],f[i-2])$。要求的答案即为 $f$最后两个位置的数中较小的那个。代码如下：

public class Solution {/*** @param cost: an array* @return: minimum cost to reach the top of the floor*/public int minCostClimbingStairs(int[] cost) {// Write your code hereif (cost == null || cost.length == 0) {return 0;}int len = cost.length;if (len == 1 || len == 2) {return cost[len - 1];}int[] dp = new int[len];dp[0] = cost[0];dp[1] = cost[1];// 开始递推for (int i = 2; i < len; i++) {dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);}return Math.min(dp[len - 1], dp[len - 2]);}
}

时空复杂度 $O(n)$。