-
Notifications
You must be signed in to change notification settings - Fork 0
/
Climbing_Stairs
40 lines (37 loc) · 1.53 KB
/
Climbing_Stairs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* Programmer : Dhruv Patel
* Problem Name : Climbing_Stairs
* Used In : leetcode
* Used As : Dynamic_Programming Problem
* Thoughts =>
* There are several approaches to tackle this problem with recursion, DP, iteration.I have used Dynamic_Programming
* approach to solving this problem.The variable n denotes total stairs to climb.climbStairs function return the
* the number of distinct ways to climb the stairs by calling helper function.The helper function iterate
* on various values to compute the result.
*/
package climbing_stairs;
public class Climbing_Stairs {
public static int climbStairs(int n) { // We take input the total number of distinct steps to climb.
if(n<=1){
return 1;
}
int dp[] = new int[n+1]; // Initializing the dp array with n+1 size
dp[1]=1; // The first step can only be climbed up in one way
dp[2]=2; // The second step can only be climbed up in two ways
return helper(n,dp);
}
public static int helper(int n,int[] dp){
if(n<=2){
return dp[n];
}
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
public static void main(String[] args) {
System.out.println(climbStairs(1));
System.out.println(climbStairs(2));
System.out.println(climbStairs(3));
System.out.println(climbStairs(4));
}
}