每日一练：【动态规划算法】斐波那契数列模型之使用最小花费爬楼梯（easy）

1. 题目链接：746. 使用最小花费爬楼梯

2. 题目描述

根据一般的思维，我们会认为本题中数组的最后一个位置是楼顶，但是根据第一个例子，如果最后一个位置是楼顶，花费最少应该为10，但是结果是15，因此本体中的楼顶指的是数组外的下一个位置。

动态规划算法对于一维数组来说，我们的思路是创建动态表dp，定义dp[i]的含义，然后根据含义去利用dp表之前或者之后的值去表示dp[i],对于本道题，两种思路，都可行，因此，本体两种方法都介绍一下。

3. 解法（动态规划）

解法一：

1. 状态表示：

我们根据题目要求，我们设dp[i]以i为结尾，跳到i台阶的最小花费

2. 状态转移方程：

我们现在要尝试根据dp[i]位置之前或之后的值去表示出dp[i]。

因为一次可以跳一阶或者两阶，所以跳到第i阶之前最近的状态，要么跳到i - 1,然后再支付cost[i - 1]，向上跳到i;要么跳到i - 2,再支付cost[i - 2],跳到i。

那么基于上述两种情况，dp[i]就有两种取值，因为求最小，我们取两个之中最小的值。

那么 状态表示方程就是dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])

3. 初始化：

我们初始化要保证不能出现越界的情况，对于上述方程，我们发现dp[0]、dp[1]，取前两个值会越界，因此，我们根据题意初始化这两个值。

4. 填表顺序：

根据状态表示方程，我们要先知道dp[i - 1]、dp[i - 2],才能知道dp[i],填dp表顺序是从左往右。

5. 返回值：

返回到达楼顶的最小花费，即dp[n].

算法代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp( n + 1);

        for(int i = 2; i <= n;i++)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }
};

解法二：

1. 状态表示：

我们设dp[i]的含义为从i出发，到达楼顶的最小花费。

2. 状态转移方程：

那么此时的最近状态是，从i出发支付第i阶的费用，然后向后跳一阶到达i + 1,或者向后跳两阶到达i + 2。

那么求从i出发到楼顶的最小花费，就是当前i阶的花费加上从i + 1出发 的最小花费或从i + 2出发的最小花费，即状态表示方程是dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);

3. 初始化：

当前状况下的边界情况，我们发现从n - 2往后跳两步或者从n - 1出发往后跳一步，就会到达楼顶，这时我们仅需要支付cost[n - 2]和cost[n - 1]的费用， 即dp[n - 2] = cost[n - 2]，dp[n - 1] = cost[n - 1]。

4. 填表顺序：

此时我们需要知道dp[i]位置值，我们需要先知道dp[i + 1]、dp[i + 2]，因此填表顺序是从右往左。

5. 返回值：

由题意知，我们可以从0阶或者1阶出发，因此为此时dp[0]表示从0出发到达楼顶的最小花费，dp[1]表示从1出发到达楼顶的最小花费，因此，我们取两者之间的最小值返回。

算法代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n);
        dp[n - 2] = cost[n - 2];
        dp[n - 1] = cost[n - 1];
        for(int i = n - 3; i >= 0;i--)
        {
            dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
        }

        return min(dp[0],dp[1]);
    }
};