爬楼梯 Leetcode 70

Question

我知道按钮向上的方法，但我试图通过记忆和使用数组而不是哈希图来解决它，你可以在互联网上找到它。但是，显然使用数组会导致 leetcode 上的 Time Limit Exceeded 错误，但它不应该而且我无法弄清楚问题是什么。有人对我的代码提交失败有什么看法吗？

class Solution {
    
    public int climbStairs(int n) {
        if(n<3) return n;
        Integer[] dp= new Integer[n+1];
        return climbStairs(n,dp);
    }
    
    private int climbStairs(int n,Integer[]dp){
        if(n<3) return n;
        if(dp[n]!=null) return dp[n];
        
        int step1=climbStairs(n-2);
        int step2=climbStairs(n-1);
        dp[n]=step1+step2;
        return dp[n];
    }
}

Answer 1

你可以使用斐波那契数列来解决这个问题

这是我通过所有测试用例的代码

public int ClimbStairs(int n) 
{
    
        //FIBONACCI SOLUTION

        // base cases
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;

        int one = 2;
        int two = 1;
        int temp = 0;

        for (int i = 2; i < n; i++)
        {
            temp = one + two;
            two = one;
            one = temp;
        }
        return temp;
    
}

Answer 2

这个问题可以用记忆化的动态规划来解决

1. 递归方法
2. 类似于斐波那契数列的迭代方法

解决方案解释：https://youtube.com/live/haFFgp3yYMQ