动态规划--使用最小花费爬楼梯

发布时间:2023年12月25日

?个人主页:Lei宝啊?

愿所有美好如期而遇


本体题目链接icon-default.png?t=N7T8https://leetcode.cn/problems/GzCJIP/

示例图示

?

?

本题动态规划解释

动态规划,如果真要清楚理解的话,可能一开始学习不太可能,专有名词太多,我们就先简单理解。

状态表示,状态转移方程,初始化,填表顺序,返回值,也就分这么几个步骤,也许你不理解,那就对了,我们分开简单说。

状态表示,也就是建一个数组,我们叫做dp表(动态规划缩写),数组每个值都对应一个状态,本题来说,dp[i]就表示到达第i个台阶的最低花费。我们如何得到他的状态,经验+题目分析(这不是废话嘛),简单来说,多做题,上百道就差不多有感觉了(滑稽)。

状态转移方程,就是dp[i]等于什么,我们图示已然分析出来:

dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。

初始化,给初始的几个状态赋值。我们为了避免越界,给dp[1]和dp[0]赋初值0。

填表顺序,就是根据状态转移方程填dp表。

返回值,返回哪个位置的值呢?由你决定。

?

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        vector<int> v(cost.size() + 1);

        for(int i=2; i<= cost.size(); i++)
        {
            v[i] = min(v[i-1]+cost[i-1],v[i-2]+cost[i-2]);
        }

        return v[cost.size()];
    }
};

文章来源:https://blog.csdn.net/m0_74824254/article/details/135193973
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。