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

最小花费爬楼梯

https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7

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)
全部评论

相关推荐

待现的未见之事:起码第一句要把自己的优势说出来吧。比如什么xx本27届学生,随时到岗....
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务