At the beginning when we want to recursively solve a problem on LeetCode, what do you come up in your mind? It is terminologies like Divide and Conquer ∪ Dynamic Programming ∪ Backtracking(searching with BFS or DFS).

Divide and conquer partitions the problems into disjoint subproblems and solves the problems recursively, and then combine the solutions to solve the original problem. Dynamic programming is an optimized Divide and conquer, which solves each sub-problem only once and save its answer in a table. There is no recursion. The key in dynamic programming is memoization. Dynamic programming applies when the subproblems overlap — that is, when subproblems share subproblems.

For me, it is a lot easier to use two recursion functions to show the difference of each other.

• Divide and Conquer: T(n)=aT(n/b)+f(n), (for problems that each element can be added to the result or not, usually half and half, normally with lower complexity than brute force, and no need of memoization)
• Dynamic Programming: T(n) = T(n-1)+T(n-2)+…+f(n). (for problems that need to split,cutting 2^n, we can use memoization and iterative method). Two ways to implement dp, bottom-to-top and top-to-bottom.

However, Backtracking searching which usually we see problems in the form of combination and permutation, it is just a way to enumerate all the solutions that is within the constraint condition.

Note: It is very important to differentiate these two subcategories, lessons learned from one Facebook interview.

Normal steps:

1. Draw examples, then we use a recursion-tree to “divide” the problems into subproblems.2. Solve the “base Case”, whose size usually is 1.3. Merge the results from the subproblems.4. Observe for possible optimization, repeated subprolems we can use “memorization”4. Use coding language to streamline the process5. check more edge cases, and the indexes, e.g. low, high, mid6. Analyze the time and space complexity

Warning: Divide and Conquer can be used to solve the problems. However, it cant get to Best Conveivable Runtime (BCR). For array it is O(n). Therefore, when we brain storming to find better solution, think about other algorithms. For array/string: Sliding window, two pointers with O(n).

For dynamic programming, it is very important to come up with the recursion function. Commonly we have:

• T(n)=T(n-1)+T(n-2)+…+T(n-k). k in [1,n-1]
• T(n)=max(cost+T(left1), T(left2)), for optimization problems, choose or not choose.
• T(n)=T(0,i-1)optT(i+1,n) (i=[1,n]), including a for loop to set up splitting position i. opt is used to connect the return result of each side, two states are split or not split yet.

Two approaches :

• bottom-up (iterative): we build the solution for one case off of the previous case (or multiple cases), for fibonacci(3)=fibonacci(2)+fibonacci(1), then we go to fibonacci(4). Time complexity is O(n), the same with top-down with memorization (DP+Memo).

Normally: 1. base cases() and special cases 2. update function, 3. goal, what is the return. And it is harder to write compared with top-down recursive solutions

• Top-down (recursive): in this case, we think about how to divide the problem for the case N into subproblems. Normally we use recursive and memo.

Note: recursive algorithms can be very space inefficient. Each recursive call adds a new layer to the stack, which means that if your algorithm recurses to a depth of n, it uses at least O(n) memory.

For this reason, it’s often better to implement a recursive algorithm iteratively. All recursive algorithms can be implemented iteratively, although sometimes the code to do so is much more complex. Before diving into the recursive code, ask yourself how hard it would be to implement it iteratively, and discuss the tradeoffs with your interviewers.