每日一题10_动态规划

题目：70. 爬楼梯

思路：

转移方程：斐波那契数列

代码：

class Solution {
    public int climbStairs(int n) {
        //a[n]=a[n-1]+a[n-2],a1=1,a2=2;   关键
        return A(n);   
    }
    int result[]=new int[100000];  //减少重复，降低复杂度
    public int A(int n){
        if(n==1||n==2) {
            return n;
        }
        if(result[n]!=0) return result[n];
        return result[n]=A(n-1)+A(n-2);
        
    }
}

官方解答:

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    

public class Solution {
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) Math.round(fibn / sqrt5);
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。