Recursion: Davis' Staircase Discussions | | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Recursion: Davis' Staircase
  2. Discussions

Recursion: Davis' Staircase

Sort by

recency

|

410 Discussions

|

  • 1337er
     + 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)

  • ygorsansone
     + 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]

  • sonali9696
     + 0 comments

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

  • gauravgargdsb
     + 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;

    }

  • urossevkusic
     + 0 comments

    O(logN) solution:

    std::vector<std::vector<int>> sq_mul(const std::vector<std::vector<int>> &A, const std::vector<std::vector<int>> &B, long long m) {
    std::vector<std::vector<int>> C(A.size(), std::vector<int>(B[0].size()));
    for(int i = 0; i < A.size(); ++i) {
        for(int j = 0; j < B[0].size(); ++j) {
            int s = 0;
            for(int k = 0; k < B.size(); ++k) {
                s += A[i][k] * B[k][j];
                s %= m;
            }
            C[i][j] = s;
        }
    }
    return C;
}

int lin_rec(std::vector<std::vector<int>> M, const std::vector<int>& M0, int N, long long m) {
    if(N < M0.size()) return M0[N];
    N -= M0.size() - 1;
    std::vector<std::vector<int>> R(M0.size(), std::vector<int>(M0.size()));
    for(int i = 0; i < M0.size(); ++i) {
        R[i][i] = 1;
    }
    while(N) {
        if(N & 1) {
            R = sq_mul(R, M, m);
        }
        N >>= 1;
        M = sq_mul(M, M, m);
    }
    
    int s = 0;
    for(int j = 0; j < M0.size(); ++j) {
        s += R[M0.size() - 1][j] * M0[j];
        s %= m;
    }
    return s;
}


long long stepPerms(long long n) {
    // 1, 2, 3
    // Fn = Fn-1 + Fn-2 + Fn-3
    std::vector<std::vector<int>> M = {{0, 1, 0}, {0, 0, 1}, {1, 1, 1}};
    std::vector<int> M0 = {1, 1, 2};
    return lin_rec(M, M0, n, 1e10 + 7);
}