首页 > 代码库 > Climbing Stairs leetcode java
Climbing Stairs leetcode java
题目：
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?
题解：
这道题就是经典的讲解最简单的DP问题的问题。。
假设现在在已经爬上来了，你之前那一步是怎么爬的，只有两种选择，1步上来的，或者2步上来的。顺藤摸瓜。写好初始条件。。
dp[i]表示从最底层到梯子顶总共有几种爬法。
所以最后的爬法就是： 你爬到还有一步到终点的爬法 加上 你还有两步到终点的爬法 。（因为这两种方法不会产生更多的爬法，唯一性）。
所以递推公式就可以写为： dp[i] = dp[i-1] + dp[i-2]
代码如下：
1 public int climbStairs(int n) {
2 if(n==0||n==1||n==2)
3 return n;
4 int [] dp = new int[n+1];
5 dp[0]=0;
6 dp[1]=1;
7 dp[2]=2;
8
9 for(int i = 3; i<n+1;i++){
10 dp[i] = dp[i-1]+dp[i-2];
11 }
12 return dp[n];
13 }
2 if(n==0||n==1||n==2)
3 return n;
4 int [] dp = new int[n+1];
5 dp[0]=0;
6 dp[1]=1;
7 dp[2]=2;
8
9 for(int i = 3; i<n+1;i++){
10 dp[i] = dp[i-1]+dp[i-2];
11 }
12 return dp[n];
13 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。