思路：
这题与LeetCode198题“打家劫舍”属于相同题型，都涉及到动态规划。
对于第i阶楼梯来说，有两种情况，要么走第i阶楼梯，要么直接跨过第i阶楼梯。而最终要求从1阶登过i阶的最小总花费c...
![\"\"](\"/images/csdn/1545618986FG15456tz18986.png\")
思路：
这题与LeetCode198题“打家劫舍”属于相同题型，都涉及到动态规划。
对于第i阶楼梯来说，有两种情况，要么走第i阶楼梯，要么直接跨过第i阶楼梯。而最终要求从1阶登过i阶的最小总花费cost(i)就可以用下面的公式表示：
cost(i) = min(“走i阶时的最小总花费”，“跨过i阶时的最小总花费”)
接下来对这两种情况进行讨论。
1)走i阶时的最小总花费
首先要明确题目的要求，就是每次只能上1级或2级。因此如果走了第i阶的话，那么之前一阶可以是i-1也可以是i-2，所以走i阶时的最小总花费就可以用下面的公式表示：
走i阶时的最小总花费 = min( value(i) + cost(i-1) , value(i) + cost(i-2) )
2) 跨过i阶时的最小总花费
同样，这种情况也要基于每次只能上1级或2级的前提。所以，如果直接跨过了第i阶台阶的话，那么之前一步必须是在i-1阶，那么跨过i阶时的最小总花费就可以用下面的公式表示：
跨过i阶时的最小总花费 = cost( i-1 )
分析到这里，就可以很自然的想到用动态规划的思想从前往后依次求的cost( j )的值并最终求得cost( i )了。
动态规划求解
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
if(len == 0)
return 0;
if(len == 1)
return cost[0];
if(len == 2)
return Math.min(cost[0],cost[1]);
//从前往后依次求出走上每一级台阶时的最小花费
for(int i=2;i<len;i++){
cost[i] = Math.min(cost[i-1]+cost[i],cost[i]+cost[i-2]);
}
return Math.min(cost[len-1],cost[len-2]);
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：涨姿势：用Python完成15位18位身份证的互转 下一篇：主题模型LDA
