Recursion: Davis' Staircase Discussions | | HackerRank

Recursion: Davis' Staircase

Sort by

recency

|

411 Discussions

|

  • + 0 comments
    def stepPerms(n):
        memo = [-1] * (n+1)
        res = countSteps(n, memo) % 10000000007
        return res
    
    def countSteps(n, memo):
        if n == 0:
            return 1 # Stay where you are
        if n == 1:
            return 1 # There is only 1 way to reach on top by takine 1 step
        if n == 2: 
            return 2 # There are 2 ways 1+1 or 2
        if n == 3:
            return 4 # There are 4 ways 1+1+1 or 2+1 or 1+2 or 3
        if memo[n] != -1:
            return memo[n]
        memo[n] = countSteps(n-1, memo) + countSteps(n-2, memo) + countSteps(n-3, memo)
        return memo[n]
        
    
  • + 0 comments
    memo = {1: 1, 2: 2, 3: 4}
    
    def r(n):
        # Write your code here
        if n <= 0:
            return 0
        if n in memo:
            return memo[n]
        result = r(n-1) + r(n-2) + r(n-3)
        memo[n] = result
        return result
        
    def stepPerms(n):
        return r(n) % (10**10 + 7)
    
  • + 0 comments

    Python with dynamic programming

    def stepPerms(n, memo=None):
        if memo is None:
            memo = [None] * (n + 1)
        if n == 0:
            return 1
        if n < 0:
            return 0
        if memo[n] is None:
            memo[n] = stepPerms(n-1, memo) + stepPerms(n-2, memo) + stepPerms(n-3, memo)
        return memo[n]
    
  • + 0 comments

    Why is n = 0 (base case), the ans is 1 not 0?

  • + 0 comments

    Recursion function to avoid TLE :

    int solve(int n, int index, vector &dp){

    if(index == n){
        return 1;
    }
    if(index > n){
        return 0;
    }
    if(dp[index]!=-1){
        return dp[index];
    }
    return dp[index] = solve(n,index+1, dp)+solve(n,index+2, dp)+solve(n,index+3, dp);    
    

    }

    int stepPerms(int n) { vectordp(n+1,-1); int ans = solve(n, 0, dp) % mod;

    return ans;
    

    }