Recursion: Davis' Staircase Discussions | | HackerRank

Recursion: Davis' Staircase

  • + 11 comments

    You can use recursion to solve this problem with a cache.

    private static Map<Integer, Integer> map = new HashMap<>();
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        for(int a0 = 0; a0 < s; a0++){
            int n = in.nextInt();
    
            System.out.println(climb(n));
        }
    }
    
    private static int climb(int n) {
        if(n < 0)
            return 0;
    
        if(n == 0)
            return 1;
    
        if(!map.containsKey(n)) {
            int count = climb(n-1) + climb(n-2) + climb(n-3);
            map.put(n, count);
        }
        return map.get(n);
    }
    
    • + 0 comments

      I did the same but I cached the 3 recursions everytime... sigh

    • + 0 comments

      give input 1 30 your code will crash!

    • + 1 comment

      Same solution in PyPy3! Speed up was enough to pass all cases but python3 is still too slow. Idea is to check if you have already calculated value for n, and if not then to add it to the dictionary.

      seen = {0: 1}
      
      def combine(n):
          if n < 0:
              return 0
          if n in seen:
              return seen[n]
          
          ret = combine(n - 1)
          ret += combine(n - 2)
          ret += combine(n - 3)
          seen[n] = ret
          return ret
      
      • + 0 comments

        That was useful @adding stuff to dictionary.

    • + 0 comments

      I totally did the same thing.

    • + 1 comment

      Did a similar python approach

      steps=[1,2,3]
      cache={}
      
      def climb(n):
          global cache
          leaves=0
      
          if n < 0: return
          for s in steps:
              if n - s >= 0:
                  if cache.has_key(n-s):
                      subres=cache[(n-s)]
                  else:
                      subres=climb(n - s)
                      cache[(n - s)] = subres
                  leaves+=subres
              if n - s == 0:
                  leaves += 1
          return leaves
      

      and climb(240) returns 2028382748046767387253483395022331055100978649577557465746184401

      with no pain at all ;)

      • + 0 comments

        You can also use the @functools.lru_cache() decorator.

    • + 0 comments

      Worked like a charm in Python3! No problem with big numbers too.

      dict = {0:0, 1:1, 2:2, 3:4}
      
      def steps(n):
          if n in dict.keys():
              return dict.get(n)
          result = steps(n-3) + steps(n-2) + steps(n-1)
          dict.update({n: result})
          return dict.get(n)
      
    • + 1 comment

      I also did it like yours

      #include <vector>
      #include <iostream>
      using namespace std;
      
      vector<int> W(37,0);
      
      int f(int n){
        return W[n] ? W[n] : W[n] = n>=3 ? f(n-3)+f(n-2)+f(n-1) : (n>>1)+1;
      }
      
      int main() {
          int n;cin>>n; //ignoring s
          while(cin>>n and cout<<f(n)<<endl);
          return 0;
      }
      
      • + 1 comment

        could you please explain you code??

        • + 2 comments

          My solution uses recursion and memoization (Dynamic Programming). It's more readable if you see it this way:

          #include <vector>
          #include <iostream>
          using namespace std;
          
          vector<int> W(37,0);
          
          int f(int n){
              if(W[n]!=0) //It had already been calculated
                  return W[n];
              else{
                  if(n>=3)
                      W[n]=f(n-3)+f(n-2)+f(n-1);
                  else if(n==1 or n==2)
                      W[n]=n;
                  else //n == 0
                      W[n]=1;
                  //these last two are this: (n>>1)+1
              }
              return W[n];
          }
          
          int main() {
              int n;cin>>n; //ignoring s
              while(cin>>n and cout<<f(n)<<endl);
              //Here I read and write until the whole input stream has been read
              return 0;
          }
          

          Sorry my english

          • + 0 comments

            Thank you for your detailed explanation.

            I got your entire DP code. Only one doubt I have and it is related to ways to calculate 3 steped staircase.

            Code says it is w[3] = w[0]+w[1]+2[2]=0+1+2=3 where as one can climb it with four different combinations.. Here it is 1 (1+1+1), 2 as (1+2), 3 as (2+1) and fourth as (3) all 3 steps in a go.

            Am i missing something?

    • + 0 comments

      A simple version to your code:

          private static int stepPerms(int n) {
                  if(n < 0)
                      return 0;
      
                  if(n == 0)
                      return 1;
      
               return  map.computeIfAbsent(n, key -> stepPerms(key-1) + stepPerms(key-2) + stepPerms(key-3));
              }
      
    • + 0 comments

      Niiiiiice! The map fixed my termination due to timeout!

    • + 1 comment

      I am not able to understand this solution. Can you please explain?

      • + 0 comments

        Check out memoization and dynamic programming: https://www.youtube.com/watch?v=P8Xa2BitN3I