Climbing stairs using DP
I started interview prep playlist of leetcode called blind - 75 and took Dynamic programming topic for solving and came across this problem climbing stairs
Logic is simple .Let us take an example
n = 1 means there is 1 stair and number of steps required for 1 stair is one (common sense)
n = 2 means there are 2 stairs and number of combinations of steps for 2 stairs is 2 (1,1 & 2)
n = 3 , you can reach to stair 3 from stair 1 by 2 steps and from stair 2 by one step,so number of combinations depend on number of combination required to reach previous two steps.
code =>
int climbStairs(int n){
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
int arr[n]; //init
arr[0] = 1; //number of ways to climb to 1st step is 1
arr[1] = 2; //number of ways to climb to 2nd step is 2
for(int i = 2 ; i < n ; i++){
arr[i] = arr[i-1] + arr[i-2];
}
printf("\n");
for(int i = 0 ; i < n ; i++){
printf("%d ",arr[i]);
}
return arr[n-1];
}