leetcode 746. Min Cost Climbing Stairs 走台阶问题 + 斐波拉契序列 + 动态规划DP

迷南。 2022-06-03 08:55 144阅读 0赞

On a staircase, the i-th step has some non-negative cost cost\[i\] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:  
Input: cost = \[10, 15, 20\]  
Output: 15  
Explanation: Cheapest is start on cost\[1\], pay that cost and go to the top.  
Example 2:  
Input: cost = \[1, 100, 1, 1, 1, 100, 1, 1, 100, 1\]  
Output: 6  
Explanation: Cheapest is start on cost\[0\], and only step on 1s, skipping cost\[3\].  
Note:  
cost will have a length in the range \[2, 1000\].  
Every cost\[i\] will be an integer in the range \[0, 999\].

考察的就是斐波拉契序列

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int minCostClimbingStairs(vector<int>& cost) 
        {
            int n = cost.size();
            vector<int> dp(n,0);
            dp[0] = cost[0];
            dp[1] = cost[1];
            for (int i = 2; i < n; i++)
                dp[i] = cost[i] + min(dp[i-1],dp[i-2]);
            return min(dp[n - 1], dp[n - 2]);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划问题--斐波那契数列

动态规划问题--斐波那契数列 1 斐波那契数列斐波那契数列其表达式如下： ![20210510233712765.png][] 2 递归算法通过公式我们不难看

﹏ヽ暗。殇╰゛Y/ 2023年01月19日 14:56/ 0 赞/ 167 阅读

相关 LeetCode：746. Min Cost Climbing Stairs使用最小花费爬楼梯（C语言）

题目描述：数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯

超、凢脫俗/ 2022年12月29日 09:19/ 0 赞/ 116 阅读

相关斐波拉契数列(动态规划)

基于动态规划来解决斐波拉契数列，替代递归的方式求解。个人觉的递归最大的问题就是会有许多的重复计算，但是动态规划通过将中间过程数据保存下来，大大节省了重复计算的量。

喜欢ヅ旅行/ 2022年08月29日 12:51/ 0 赞/ 173 阅读

相关 leetcode 70. Climbing Stairs DP动态规划 + 斐波那契序列

You are climbing a stair case. It takes n steps to reach to the top. Each time you can

落日映苍穹つ/ 2022年06月09日 11:56/ 0 赞/ 134 阅读

相关 leetcode 746. Min Cost Climbing Stairs 走台阶问题 + 斐波拉契序列 + 动态规划DP

On a staircase, the i-th step has some non-negative cost cost\[i\] assigned (0 indexed).

迷南。/ 2022年06月03日 08:55/ 0 赞/ 145 阅读

相关 746.Min Cost Climbing Stairs

> On a staircase, the i-th step has some non-negative cost cost\[i\] > assigned (0 ind

红太狼/ 2022年05月30日 06:38/ 0 赞/ 126 阅读

相关 746. Min Cost Climbing Stairs

数组的每个索引做为一个阶梯，第 `i`个阶梯对应着一个非负数的体力花费值 cost\[i\](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继

一时失言乱红尘/ 2022年05月26日 23:07/ 0 赞/ 122 阅读

相关 Min Cost Climbing Stairs

Min Cost Climbing Stairs 题目 On a staircase, the `i`\-th step has some non-negative

绝地灬酷狼/ 2022年05月14日 06:19/ 0 赞/ 136 阅读

相关【Leetcode】70. Climbing Stairs（动态规划）

You are climbing a stair case. It takes n steps to reach to the top. Each time you can

野性酷女/ 2022年04月23日 15:18/ 0 赞/ 148 阅读

相关动态规划斐波那契

运用动态规划描述斐波那契数列，运用动态规划使得问题简化，运算速度大幅提升。 private static int fib(int n) { if(n==

淩亂°似流年/ 2022年02月02日 11:15/ 0 赞/ 233 阅读