[Recursion and Dynamic Programming] interview questions #1

[rygh4775]

Triple Step: A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

[RoyMoon]

다이나믹 프로그래밍을 사용한 해법

class Solution {
 public :
  int climbStairs(){
    int input; 
    cin >> input;
    cout << "input : " << input  << endl;
    if(input <= 0) return 0; 
    if(input == 1) return 1; 
    if(input == 2) return 2; 
    if(input == 3) return 4; 
    vector<int> dp; dp.resize(input+1);
    dp[0] =0;
    dp[1] =1;
    dp[2] =2;
    dp[3] =4;
    for(int i =4; i <= input; ++i) {
      dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    return dp[input];
  }
};

int main()
{
    auto s = new Solution();
    cout << "output : " << s->climbStairs();

    return 0;
}

Time Complexity O(n)

[btakeya]

with recursion:

1. simple implementation, but too slow due to too many recursive calls

2. we can solve problem faced at 1 with memoization

   
   def step_without_memoization(height):
   def go(remain):
       if remain < 0:
           return 0
       elif remain == 0:
           return 1
       else:
           return go(remain - 1) + go(remain - 2) + go(remain - 3)
   
   return go(height)

def step_with_memoization(height): memory = [-1] * (height + 1) def go(remain): if remain < 0: return 0 elif remain == 0: return 1 elif memory[remain] > -1: # if memoized exists return memory[remain] else: memory[remain] = go(remain - 1) + go(remain - 2) + go(remain - 3)

        return memory[remain]

return go(height)

def step(height):

return step_without_memoization(height)

return step_with_memoization(height)

if name == 'main': height = int(input()) count = step(height) print(count)

one more thing: problem can be solved with recursive is also can be solved with loop (a.k.a. dynamic programming)

[btakeya]

• time complexity: O(n), n is whole steps of stair
• space complexity: O(n), n is whole steps of stair