LeetCode - Easy - 70. Climbing Stairs-蒲公英云

LeetCode - Easy - 70. Climbing Stairs

Topic

Dynamic Programming

Description

https://leetcode.com/problems/climbing-stairs/

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

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

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 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

Constraints:

1 <= n <= 45

Analysis

逐步分析，找出其中的规律。设f(n)为在n个阶梯上，每步1或2个阶梯，则有多少种方式登上顶。

由题目得f(1)=1，f(2)=2，f(3)=3。

n = 4，则有以下方案

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

总共有5种方案，观察其中规律：当第1步走1个阶梯，剩下有f(3)=3种走法（13加粗的部分），当第1步走2个阶梯，剩下有f(2)=2种走法（45加粗的部分）。

可得f(4)=f(3)+f(2)。那么，大胆推测一下，f(n) = f(n-1) + f(n-2)。我们再举n=5实证一下。

n = 5，则有以下方案

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 2 + 1
1 + 2 + 1 + 1
1 + 2 + 2
2 + 1 + 1 + 1
2 + 1 + 2
2 + 2 + 1

总共有8种方案，观察其中规律：当第1步走1个阶梯，剩下有f(4)=5种走法（15加粗的部分），当第1步走2个阶梯，剩下有f(3)=3种走法（68加粗的部分）。可得f(5)=f(4)+f(3)

因此，表达式f(n) = f(n-1) + f(n-2) 应该就是解决这题目的关键。

f(n) = f(n-1) + f(n-2)，这不就是斐波那契数列，当初学递归时接触的经典数列。

代码实现方法：

方法一：递归法，另分配数组作缓存
方法二：迭代法
方法三：尾递归法

Submission

public class ClimbingStairs { 
    //方法二：
    public int climbStairs1(int n) { 
        if (n == 1 || n == 2)
            return n;
        int first = 1, second = 2;
        for (int i = 2; i < n; i++) { 
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }
    //方法三：
    public int climbStairs2(int n) { 
        if (n == 1)
            return 1;
        return climbStairs2(1, 2, n, 2);
    }
    private int climbStairs2(int first, int second, int num, int index) { 
        return index == num ? second : climbStairs2(second, first + second, num, index + 1);
    }
    //方法二：别人写的
    public int climbStairs3(int n) { 
        int a = 1, b = 1;
        while (n-- > 0)
            a = (b += a) - a;
        return a;
    }
}

Test

import static org.junit.Assert.*;
import org.junit.Test;
public class ClimbingStairsTest { 
    @Test
    public void test() { 
        ClimbingStairs obj = new ClimbingStairs();
        assertEquals(1, obj.climbStairs1(1));
        assertEquals(2, obj.climbStairs1(2));
        assertEquals(3, obj.climbStairs1(3));
        assertEquals(5, obj.climbStairs1(4));
        assertEquals(8, obj.climbStairs1(5));
        assertEquals(1, obj.climbStairs2(1));
        assertEquals(2, obj.climbStairs2(2));
        assertEquals(3, obj.climbStairs2(3));
        assertEquals(5, obj.climbStairs2(4));
        assertEquals(8, obj.climbStairs2(5));
        for(int i = 1; i <= 100; i++) { 
            assertEquals(obj.climbStairs1(i), obj.climbStairs2(i));
            assertEquals(obj.climbStairs1(i), obj.climbStairs3(i));
        }
    }
}