爬楼梯

问题陈述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**注意：**给定 n 是一个正整数。

思路分析

可考虑动态规划进行解决，每次只能爬一阶或两阶，也就是当前位置只能由前一个位置或前两个位置得到，于是列出转移方程dp[i]=dp[i-1]+dp[i-2]，即两种情况加和。继续判断起始情况，当台阶数为0，定义可能爬楼梯的情况为1，只有只有后面计算才符合转移方程；当台阶数为1，可能爬楼梯的情况为1。最后爬完楼梯，可能的情况就是dp[n]。

代码实现

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;
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }
}