【Check 69】2024-05-09 - 70. 爬楼梯

[larscheng]

70. 爬楼梯

[larscheng]

思路

根据题意：每次可以上1级或者2级，到达n级有两种情况，从n-1级走1级到达；从n-2级走2级到达 f(n)=到达n级的走法，f(n)=f(n-1)+f(n-2) 特殊情况：f(1)=1，f(2)=2 通过递归，收集结果

代码

    class Solution1 {
        //从n反过来看，从n-1级和n-2级都可以到达n级楼梯，所以f(n)=f(n-1)+f(n-2)
        //再看特殊case，n=1和n=2
        //递归计算f(n)
        //O(n*n)/O(1)
        //优化点：存在重复计算 f(n)=f(n-1)+f(n-2), f(n-1)=f(n-2)+f(n-3)  f(n-2)就多算了一次
        public int climbStairs(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }
}

复杂度

• 时间复杂度：O(n*n)
• 空间复杂度：O(1)

[larscheng]

思路

纯递归的优化点：存在重复计算 f(n)=f(n-1)+f(n-2), f(n-1)=f(n-2)+f(n-3) f(n-2)就多算了一次 用哈希表记录算过的结果，进行记忆化递归

代码

class Solution2 {

        Map<Integer,Integer> mem = new HashMap<>();
        public int climbStairs(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            if (mem.containsKey(n)){
                return mem.get(n);
            }

            int fn = climbStairs(n - 1) + climbStairs(n - 2);
            mem.put(n, fn);

            return fn;
        }
    }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[larscheng]

思路

已知fn=fn-1+fn-2，可以通过动态规划，临界值n=1和n=2

代码

    class Solution3 {

        public int climbStairs(int n) {
            if (n <= 2) {
                return n;
            }
            int[] dp = new int[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];
        }
    }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[larscheng]

思路

动态规划中发现，每次关注的都是n-1和n-2，可以进行空间优化 利用滚动变量取代dp数组

代码

class Solution {

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int x = 1, y = 2;
        int sum;
        for (int i = 3; i <= n; i++) {
            sum = x + y;
            x = y;
            y = sum;
        }
        return y;
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)