[数据结构与算法]746. 使用最小花费爬楼梯（动态规划dp）

题目描述：

?算法思路：

?

• 首先定义dp[i]代表的含义：定义dp[i]表示踏上第i阶台阶的最小花费。
• 确定状态方程：
• 由上图所示：到达i阶有两种方式：

1. 方式一：从i-1层跳一层，跳到i阶，然后就到达top层（结束的位置）因此：到达top需要 的花费为dp[i-1]+cost[i](爬上i-1层最小花费，加上i到top的花费cost[i])
2. 方式二：从i-1层跳两层，到达第i层，然后从i跳到top层结束，因此：到达top需要的花费为dp[i-2]+cost[i](爬上i-2层最小花费，加上i到top的花费cost[i])
3. 两种方式中取最小值作为结果。

• 初始状态初始化：由于dp[i]有dp[i-1]和dp[i-2]推理出的，所以只需要初始化dp[0]，dp[1]

1. dp[0]=cost[0]
2. dp[1]=cost[1]

代码实现：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int len=cost.size();//cost长度
        int dp[len];//定义dp数组，长度为len
        //初始化
        dp[0]=cost[0];
        dp[1]=cost[1];
        //从第2个台阶进行遍历，求解dp
        for(int i=2;i<len;i++){
            dp[i]=min(dp[i-1],dp[i-2])+cost[i];
        }
        return min(dp[len-1],dp[len-2]);
    }
};