DP-LeetCode-746. 使用最小花费爬楼梯

lexingsen

发布于 2022-02-24 18:18:07

25400

代码可运行

文章被收录于专栏：乐行僧的博客乐行僧的博客

运行总次数：0

代码可运行

思想：

闫氏DP法

状态表示

集合：f[i]表示到第i阶所花费最小的体力值
属性：min 状态计算当前第n阶台阶可以从第n-1阶台阶爬一阶或者第n-2阶台阶爬两阶到达第n阶。所花费的体力的最小值是（从第n-1阶台阶爬一阶或者第n-2阶台阶爬两阶到达第n阶中体力最小值）加上当前层所有要的体力消耗。状态转移方程，f[i] = min(f[i - 1], f[i - 2]) + cost[i];

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

        return min(f[n], f[n - 1]);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

dp