LC.P70[爬楼梯]

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int[] cache;

    public int climbStairs(int n) {
        cache = new int[n + 1];
        return dfs(n);
    }

    private int dfs(int i) {
        if (i <= 1) return 1;
        if (cache[i] != 0) return cache[i];
        return cache[i] = dfs(i - 1) + dfs(i - 2);
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：动态规划（1:1翻译成递推）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= n; ++i) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法三：空间优化

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1, c;
        for (int i = 2; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$