动态规划之使用最小花费爬楼梯

最近对动态规划算法感兴趣，在网站 leetcode 上找到了一个 “使用最小花费爬楼梯” 的题目。尝试了一下，磕磕绊绊地解决了这个算法。

题目描述如下：

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i] ,索引从0开始。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

动态规划的解题思路可以从一下考虑：回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。
回溯算法大概是把所有可能的路径都走一遍，然后从中选择一条花费最小的路径。这里就不写代码了。

最后贴一下代码：

class Solution {
public int minCostClimbingStairs(int[] cost) {
    if(cost == null || cost.length == 0 || cost.length == 1)
    {
        return 0;
    }
    int[][] status = new int[cost.length][2];
    //初始化第一行数据
    status[0][0] = 0;
    status[0][1] = cost[0];

    for(int i = 1;i<cost.length;i++)
    {
        // statas[i][0] 表示不经过第i个阶梯，未经过第i个阶梯的一定经过第i-1个阶梯
        status[i][0] = status[i-1][1];
        //statas[i][0] 表示经过第i个阶梯，经过第i个阶梯不一定经过第i-1个阶梯
        status[i][1] = cost[i] +Math.min(status[i-1][1],status[i-1][0]);
    }
    return Math.min(status[cost.length-1][0],status[cost.length-1][1]);
  }
}