Climbing Stairs

##题目

####Climbing Stairs

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?

##解题思路
该题是典型的动态规划方法,由于每次只能夸1步或2步,则到达第i层的方法数只依赖于到达第i-1层和第i-2层的方法数,因此动态规划定义如下:

定义dp[i]:到达第i层共有的方法数
则dp[i]=dp[i-1]+dp[i-2]

##算法代码
代码采用JAVA实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int climbStairs(int n) {
if(n<0)
return 0;
if(n==1)
return 1;
int[] dp=new int[n+1];//dp[i]表示到达第i层共有的方法数
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
return dp[n];

}
}

Comments