首页 > 代码库 > leetcode------Climbing Stairs
leetcode------Climbing Stairs
标题: | Climbing Stairs |
通过率: | 34% |
难度: | 简单 |
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?
刚拿到这个题,看完后第一反应是跟我算法课上学的那个回溯一样,就是0-1背包问题。树形结构就是1或者2 然后判断到终点没有。然后我感觉我想多了,应该不会是这种题型,无奈上网查了下思路,根据提示我拿纸写了几下:
1、n=0时,就是没有方法。
2、n=1时,只能走一步了。一种方法,
3、n=2时,可以直接走两步,或者一步一步走,
写到这里还是看不出来原因,接着写:
4、n=3时,先走一步,或者先走两步,先走一步后剩下的就回归到n=2,先走一步就回归到n=1;
5、n=4时,先走一步回归到n=3,先走两步回归到n=2;
由此可以看出,先走这一步是关键,只可能是两种,先走一步,或者先走两步,于是总结到了
f(n)=f(n-1)+f(n-2),让其一步一步的回归。写到这里很明显是个费波拉挈数列,网上再去查,这个就是斐波拉契数列的简单应用。
直接看代码:
1 public class Solution { 2 public int climbStairs(int n) { 3 if(n==0||n==1||n==2)return n; 4 int [] array=new int[n+1]; 5 array[0]=0; 6 array[1]=1; 7 array[2]=2; 8 for(int i=3;i<=n;i++){ 9 array[i]=array[i-1]+array[i-2];10 }11 return array[n];12 }13 }
leetcode------Climbing Stairs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。