Climbing Stairs DP Problem base case concept-CodePudding

Question: You are climbing a staircase. It takes n steps to reach the top. Each time you can either jump 1 or 2 or 3 steps. In how many total number of ways can you jump to the top?

My Explanation: Well I'm thinking of applying recursion because I can find the solution by solving similar subproblems and on that process, there will be many overlapping subproblems so I'll array data structure to save the denomination of similar subproblems so that I don't need to solve same subproblem twice. So I'm using top down DP approach.

My Doubt:

Now to build the solution, I need a base case where the program flow ends and it returns back to it's parent node(if you visualize it as a tree). So the base case what I was thinking is like when I was at the floor, at ground 0 so there will be no other ways I can reach ground 0 state, so it's the base case.

When n=0, I should return 0 or 1, that's my doubt? Well I have written the code, so the code work when I return 1, not 0 at n=0. So why I should return 1 when n=0, what's the reason behind it? Please Help!!!

My Code:

#include <iostream>
using namespace std;

int climbing_ladders_topDown(int n, int k, int dp[]){
    //Base Case
    if(n==0){
        return 1;
    }

    //LookUp
    if(dp[n]!=0){
        return dp[n];
    }

    //Recursive Case
    int total_num_of_ways = 0;
    for(int jumps=1;jumps<=k;jumps  ){
        if(n-jumps>=0){
            total_num_of_ways  = climbing_ladders_topDown(n-jumps,k,dp);
        }
    }
    
    dp[n] = total_num_of_ways;
    return dp[n];
}

int main() {
    int num_of_stairs = 4;
    int num_of_jumbs = 3;
    int dp_arr[100] = {0};

    cout<<climbing_ladders_topDown(num_of_stairs,num_of_jumbs,dp_arr);
    
    return 0;
}

Output: 7

Correct flow of Code (thanks to @appleapple):

#include <iostream>
using namespace std;

int climbing_ladders_topDown(int n, int k, int dp[]){

    //Base Case
    if(n==0){
        return 0;
    }

    //LookUp
    if(dp[n]!=0){
        return dp[n];
    }

    //Recursive Case
    int total_num_of_ways = 0;

    for(int jumps=1;jumps<=k;jumps  ){
        
        if(n-jumps > 0){
            total_num_of_ways  = climbing_ladders_topDown(n-jumps,k,dp);
        }
        
        if(n-jumps == 0){ // have reach the end or ground 0, base so no more move possible in downward direction
            total_num_of_ways  = 1; 
        }
        
        if(n-jumps < 0){ //we can't move to -ve state/underground, because it doesn't exist
            total_num_of_ways  = 0;
        }

    }
    
    dp[n] = total_num_of_ways;
    
    return dp[n];
}

int main() {

    int num_of_stairs = 4;
    int num_of_jumbs = 3;
    
    int dp_arr[100] = {0};

    cout<<climbing_ladders_topDown(num_of_stairs,num_of_jumbs,dp_arr);
    
    return 0;
}

CodePudding user response：

because you request it to be 1 here (f(0) = 1)

for(int jumps=1;jumps<=k;jumps  ){
   if(n-jumps>=0){
      total_num_of_ways  = climbing_ladders_topDown(n-jumps,k,dp); // here
   }
}

if you want f(0)=0, since recurse into f(0) doesn't really make sense anymore (there is no possible solution, just like f(-1))

the algorithm for such case would becomes

if(n<=0){
   return 0; // not possible
}
///...
for(int jumps=1;jumps<=k;jumps  ){
   if(n-jumps>0){
      total_num_of_ways  = climbing_ladders_topDown(n-jumps,k,dp);
   }
   if(n-jumps==0){ // have reach the end, no more move possible
        total_num_of_ways; // you hide this under n=0
   }
}

CodePudding user response：

In these kind of problems of counting number of ways, dp[0][..] is usually equal to 1, as there're 1 way to jump 0 step, doing nothing.

And with your problem, as you already figure out this is a DP problem, it can be solve easily with a for loop, resembling similarities to the Tribonacci sequence (https://oeis.org/A000073) with different base cases starting point:

#include <iostream>
using namespace std;

const int maxn = 1e3;

int main()
{
    int n; cin >> n;
    int dp[maxn 1];

    //base case
    dp[0] = 1; dp[1] = 1; dp[2] = 2;

    //dp
    for (int i = 3; i <= n; i  )
    {
        dp[i] = dp[i-1]   dp[i-2]   dp[i-3];
    }

    cout << dp[n];
}

Test:

Input : 3
Output : 4

Explanation : There're 4 ways : 1 1 1, 1 2, 2 1, 3.

Your way of recursion and remembering DP state isn't wrong, it's just a lot more chunky.

To be clear, setting dp[0] = 1 as a base case is just an easy and (kind of) conventional thing. You could totally do the base cases as dp[1] = 1, dp[2] = 2, dp[3] = 4 and start from dp[4].

The complexity of the code is O(n), but if you need bigger n value, check out this post : https://www.hackerearth.com/practice/notes/solving-linear-recurrence-relation/