File tree Expand file tree Collapse file tree 1 file changed +25
-0
lines changed Expand file tree Collapse file tree 1 file changed +25
-0
lines changed Original file line number Diff line number Diff line change
1
+ package easy ;
2
+
3
+ /**Leetcode 70: You are climbing a stair case. It takes n steps to reach to the top.
4
+
5
+ Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?*/
6
+ public class ClimbingStairs {
7
+ //classical dp problem
8
+ public int climbStairs (int n ) {
9
+ if (n < 1 ) return 0 ;
10
+ if (n < 4 ) return n ;
11
+ int [] dp = new int [n +1 ];
12
+ //the number of ways to reach step n could be calculated from n-1 and n-2
13
+ dp [1 ] = 1 ;
14
+ dp [2 ] = 2 ;
15
+ for (int i = 3 ; i <= n ; i ++){
16
+ dp [i ] = dp [i -1 ] + dp [i -2 ];
17
+ }
18
+ return dp [n ];
19
+ }
20
+
21
+ public static void main (String ... strings ) {
22
+ ClimbingStairs test = new ClimbingStairs ();
23
+ System .out .println (test .climbStairs (6 ));
24
+ }
25
+ }
You can’t perform that action at this time.
0 commit comments