首页 > 其他分享 >1. 斐波那契数 爬楼梯 使用最少花费爬楼梯

1. 斐波那契数 爬楼梯 使用最少花费爬楼梯

时间:2022-09-18 09:12:08浏览次数:112  
标签:契数 爬楼梯 int Solution height 斐波 cost public dp

1. 斐波那契数

版本一:一维数组记录型

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        std::vector<int > dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i<=n; ++i){
               dp[i] = dp[i-1] + dp[i-2]; 
        }
        return dp[n];
    }
};

利用一维数组进行记录。目的 明确动态规划的 的五步

  • 确定dp数组的含义
  • 确定递推公式
  • 初始化问题
  • 遍历问题
  • 日志问题

版本二:两个变量记录

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        int sum = 0;
        for(int i = 2 ;i <= n ; ++i){
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return sum;
    }
};

因为每一次都只用到前面两个的数据,因此可以简化数组。降低空间复杂度。

版本三:递归

class Solution {
public:
    int fib(int n) {
        if(n <= 1)
            return n;
        return fib(n-1) + fib(n-2);
    }
};

使用自顶向下的进行计算,中间存在重叠的子问题。可以利用一个数组进行记忆化搜索。

2. 爬楼梯

版本一:空间没有优化的版本

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2 ) return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

确定五部曲,明确每一步含义。

版本二:优化空间

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2 ) return n;
        int dp[2];
        dp[0] = 1;
        dp[1] = 2;
        int sum = 0;
        for(int i = 3; i <= n; ++i){
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

因为每一次都只是用到前面两个dp的值,返回的也只是一个对应的dp值,所以可以进行空间的优化。

3. 使用最小花费爬楼梯

版本一:没有进行空间优化

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

        return min(dp[height-1] , dp[height - 2]);
    }
};

版本二: 空间优化

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int height  = cost.size();
        if(height == 1) return cost[0];
        int dp[2] ;
        dp[0] = cost[0];
        dp[1] = cost[1];
        int dp3 = 0;
        for(int n = 2 ; n  < height; ++n){
            dp3 =  min(dp[1]  , dp[0] ) + cost[n] ;
            dp[0] = dp[1];
            dp[1] = dp3;
        }

        return min(dp[1] , dp[0]);
    }
};

标签:契数,爬楼梯,int,Solution,height,斐波,cost,public,dp
From: https://www.cnblogs.com/sansuitaibai/p/16704194.html

相关文章

  • 10.10 斐波那契数列_本章总结
      #斐波那契数列 计算  1,1,2,3,5,8  后面的数为前面两数相加deffib(n):ifn==1:return1elifn==2:return1else:......
  • python 用循环和递归分别实现斐波那契数列
    用循环和递归分别实现斐波那契数列#1\用for循环实现斐波那契数列res=[]foriinrange(10):ifi<2:res.append(1)else:res.append(res[i-......
  • 信息学奥赛一本通 1188:菲波那契数列(2)
    时间限制:1000ms      内存限制:65536KB提交数:46311   通过数:17428【题目描述】菲波那契数列是指这样的数列:数列的第一个和第二个数都为<spa......
  • CF446C(线段树+斐波那契)
    CF446C(线段树+斐波那契数列)CF链接洛谷链接题目大意:区间加斐波那契数列,区间求和分析:一眼鉴定为线段树难点在于如何打标记,合并和传递标记对于斐波那契数列有几个性......
  • C2解决斐波那契数列
    此题较为简单,只需定出后一项等于前两项之和即可代码如下1#include<stdio.h>2#defineN1003voidshow(inta[N])//定义一个函数4{5for(inti=1;i<=2......
  • CSP-S模拟1 [斐波那契,数颜色,分组]
    CSP-S模拟1洛谷上原题,不挂题面了。A.斐波那契P3938斐波那契观察上图,可发现规律:一个数的父亲等于这个数减去最大的小于它的斐波那契数。特殊的,如果这个数是斐波那契......
  • 矩阵递推斐波那契数列
      斐波那契数列都很熟悉,它满足,\(F_{n}=\begin{cases}1&n\leqslant2\\F_{n-1}+F_{n-2}&n>2\end{cases}\)。因为\(F_n\)从第三项开始是不断的递推下去的,所以......
  • 【python3.8】斐波拉契数列实现
    importtimedefmemoize(f):memo={}defhelper(x):ifxnotinmemo:memo[x]=f(x)returnmemo[x]returnhelper......
  • leetcode 斐波那契数列 javascript实现
    写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项(即F(N))。斐波那契数列的定义如下:F(0)=0,  F(1) =1F(N)=F(N-1)+F(N-2),其中N>1.斐波那契数列由0......
  • 斐波那契数列前1000项
    {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,57......