题解 | #最小花费爬楼梯#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型vector 
     * @return int整型
     */
    int minCostClimbingStairs(vector<int>& cost) {
        // write code here
        int n = cost.size();
        vector<int> f(n + 1);
        f[0] = f[1] = 0; // 从0或者1的阶梯上花费都为0
        for (int i = 2; i <= n; i++) {
            f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }

        return f[n];
    }
};

• 思路：动态规划
• 状态表示：f(i)表示跳到第i个台阶需要的最小代价
• 状态计算：f(i)有上一次跳一个台阶或者跳两个台阶的状态转移，f(i) = min(f(i - 1) + cost(i - 1), f(i - 2) + cost(i - 2))
• 时间复杂度：O(n)
• 空间复杂度：O(n)