美文网首页
动态规划--爬楼梯

动态规划--爬楼梯

作者: Pig_deng饲养员 | 来源:发表于2020-04-08 16:28 被阅读0次

    题目

    climbing-stairs
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
    注意:给定 n 是一个正整数。

    思路

    假设楼梯台阶从下到上依次标号为0、1、2、3...n。
    用f(x)代表从楼底走到第x阶有多少种方法。
    因此f(0) = 1f(1)=1
    f(2) = 2f(x) = f(x-1) + f(x-2)
    递推公式的原因是只能走到台阶x-1或台阶x-2走动台阶x。因此只要计算出f(x-1)和f(x-2)就可以得出f(x)。

    递归/回溯

    这个递推公式就是斐波那契数列,可以直接写一个递归循环。
    递归可以完成题目,但是提交之后会显示超时,因为递归很耗费时间。
    时间复杂度是2^n级别的。

    c++代码
    class Solution {
    public:
        int climbStairs(int n) {
            if(n == 0) return 1;
            else if(n == 1) return 1;
            else
            {
                return climbStairs(n-1)+climbStairs(n-2);
            }
        }
    };
    

    记忆化递归

    递归方法在进行计算的时候会出现大量重复的计算,因此可以使用数组将每一步的计算结果存储下来,这样下次可以直接使用,节省时间。
    时间复杂度:O(n)
    空间复杂度:O(n)

    c++代码
    class Solution {
    int a[1000]= {0};
    public:
        int climbStairs(int n) {
            if(n==0||n==1) 
            {
                a[n] = 1;
                return 1;
            }
    
            if(a[n]>0) return a[n];
    
            a[n] = climbStairs(n-1) + climbStairs(n-2);
    
            return a[n];
        }
    };
    

    动态规划

    先定义dp状态:定义状态dp[i]为走到楼梯i总共可以走的步数。
    定义递推公式:dp[i] = dp[i-1] + dp[i-2]
    定义初始化变量:dp[0] = 1,dp[1] = 1

    c++代码1

    使用mem数组来存储计算过的dp状态,返回数组最后的值。

    class Solution {
    public:
        int climbStairs(int n) {
            long a[100000];
    
            if(n==0 || n==1) return 1;
            a[0] = a[1] = 1;
            for(int i=2; i<=n; i++)
            {
                a[i] = a[i-1] + a[i-2];
            }
            
            return a[n];
        }
    };
    
    c++代码2

    不使用数组而是使用两个变量来储存dp[i-1]+dp[i-2],节省存储空间。
    时间复杂度O(n);
    空间复杂度O(1);

    class Solution {
    public:
        int climbStairs(int n) {
            int fn_1 = 1, fn_2 = 1,tmp;  //fn_1为dp[i-1],fn_2为dp[i-2]
            int result=0;
    
            if(n==1) return 1;
            for(int i=2; i<=n; i++)
            {
                result = fn_1 + fn_2;
                fn_1 = fn_2;
                fn_2 = result;
                
            }
            
            return result;
        }
    };
    

    相关文章

      网友评论

          本文标题:动态规划--爬楼梯

          本文链接:https://www.haomeiwen.com/subject/vfhnphtx.html