[Leetcode Pattern] - Recursion, Dynamic Programming

Preface

It’s likely to confuse the topic between recursion and dynamic programming when starting leetcode, so let we take a look what’s the difference between them and compare the use cases.

Recursion

Two types of Recursion

• Backtracking

  • Finding all solutions by exploring all potential candidates and abandoning the candidate while determining it’s not the valid solution

  • Staging the current status before jumping to next successor function and restore the status when finish the successor.

• Cascading

  • The result of the current stage can be form by the next stages, ex: fibonacci

Recursive vs Iterative

• Recursive → top-down

• Iterative → bottom up

• Trade-Off: The recursive with n-depth has at least O(n) memory consumption on the function call stack but it has intuitive implementation in some scenario

Dynamic Programming

Find the optimized final solution while traversing each state and cache the traversed states results by memorization technique.

What’s It Different from Greedy Algorithm?

• The greedy algorithm always makes the choice that seems to be the best at the current state and the result made by each best state also leads to the best final solution.

When to Use Dynamic Programming or Not?

• When solving max of.. min..of like problems.

• Kadane’s Algorithm: iterative dynamic programming algorithm

• If the time complexit is to expensive, is there any greedy solution?

How to Implement it?

• Recursive

  • Think the process as a tree structure while computing the time complexity or if you want to convert the process to iterative way.

  • Not all dynamic programming can be solved by recursive way

• Iterative

  • Usually, faster and less memory usage than the recursive way if the recursive solution exists