Leetcode(70) Climbing Stairs

发表于 | 分类于

Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解法

最开始的想法是DFS暴力搜索所有可能的情况，毫无疑问，超时了0.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    int cnt = 0;

    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        dfs(n);
        return cnt;
    }

    void dfs(int n) {
        for (int i = 1; i <= 2; i++) {
            if (n - i == 0) {
                cnt += 1;
                return;
            }
            if (n - i > 0) {
                dfs(n - i);
            } else {
                return;
            }
        }
    }
}

仔细一想，貌似可以采用动态规划的思想，因为走到台阶n有两种可能的走法，一种是从n-1迈一步上来，一种是从n-2迈2步上来，于是有dp[n] = dp[n-1] + dp[n-2]。额，这不就是斐波那契数列吗0.0

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        else{
            return climbStairs(n-1)+climbStairs(n-2);
        }
    }
}

很遗憾，还是超时了0.0。问题在于重复计算。因此，采用记忆化避免重复计算，最终成功AC~(^-^)

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] nums = new int[n + 1];
        nums[1] = 1;
        nums[2] = 2;
        return find(nums, n);

    }

    int find(int[] nums, int n) {
        if (nums[n] != 0) {
            return nums[n];
        } else {
            nums[n] = find(nums, n - 1) + find(nums, n - 2);
            return nums[n];
        }
    }
}