70.Climbing Stairs

70.Climbing Stairs

题目

你正在爬楼梯，需要花费n步到达顶端。
每次你爬1或者2步，一共有多少种不同的方式可以爬到顶端。
注意：给出的n是个正整数。

例1：
Input: 2
Output: 2

解释：有两种方式到达顶端。
法1. 1 步 + 1 步
法2. 2 步

例2：
Input: 3
Output: 3

解释：有三种方式到达顶部。
法1. 1 步 + 1 步 + 1 步
法2. 1 步 + 2 步
法3. 2 步 + 1 步

代码块

class Solution {
    public static int climbStairs(int n) {
        if(n == 1){//边界测试
            return 1;
        }
        int[] dp = new int[n];
        dp[0] = 1;//初始化
        dp[1] = 2;//初始化
        for(int k = 2 ; k < n; k++){
           dp[k] = dp[k - 1] + dp[k - 2];
        }
        return dp[n-1];
    }
    public static void main(String[] args) {
        int n = 4;
        System.out.println(climbStairs(n));
    }
}

代码分析

这个是动态规划问题。也是斐波那契数列的应用。
写代码类似于作归纳证明题。
注意边界值测试，即n=1的话就返回一。
其实就是看怎么才能到达顶端，可以由前一个，或者前两个台阶跳过来；
那么有多少种方式到达“前一个”和“前两个”呢？