2021-10-31 leetcode 动态规划 746.使用最小花费爬楼梯 c++

2021-10-31 leetcode 动态规划 746.使用最小花费爬楼梯 c++

对于题目的另外一种表述方式：
每个阶梯都有一定数量糖果，一次只能跨一个或者两个阶梯，走到一个阶梯就要吃光上面的糖果，问怎么走才能吃最少的糖果？开局你选前两个阶梯的其中一个作为开头点，并吃光该阶梯的糖果。
思路
当前吃掉的糖果数 ==当前阶梯上有的糖果数 + min(在前1阶时已吃糖果数， 在前2阶时，已吃糖果数）；
利用min函数来选择已吃糖果数更少的阶梯，以达到状态转移。
dp[i]为台阶i上的糖果数
状态转移方程：dp[i] += min(dp[i-1], dp[i-2]);

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int l = cost.size();
        int dp[l+1];
        dp[l] = 0;//注意这个值是cost没有赋予的，也就是顶楼的糖果数（0）
        for(int i = 0; i < l; i++) 
            dp[i] = cost[i];
        for(int i = 2; i <= l; i++)
            dp[i] += min(dp[i-1], dp[i-2]);
        return dp[l];
    }
};