Climbing stairs using DP

·

1 min read

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

  1. n = 1 means there is 1 stair and number of steps required for 1 stair is one (common sense)

  2. n = 2 means there are 2 stairs and number of combinations of steps for 2 stairs is 2 (1,1 & 2)

  3. 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];

}