Dynamic Programming
Here is some prior required knowledge, Recursion. Even I bet everyone who reads this are know about recursion. So will just simply go through it as a revision.
Recursion is something that many computer science majors consider elegant. A recursion function is a function where a function is calling the function itself until a “basic condition” is true, and execution stops. While false, we will keep placing execution contexts on top of the stack.
Here is an example about how to find fibonacci using recursion in python
def recur_fibo(n):
"""Recursive function to print Fibonacci sequence"""
if n <= 1:
return n
else:
return(recur_fibo(n1) + recur_fibo(n2))
print(recur_fino(6)) # answer is 8
In the realworld, some problem can only be solved by using recursion. That means, recursion is a must in some situation, or maybe just more natural to do it with recursion. Just like Fibonacci! From another point of view, recursive is just to make your code more readable and pretty.
Is there a risk for recursion? Yes. Definitely.
“Great power comes with great responsibility”  Uncle Ben
Recursive is just keep placing execution contexts on the top of the stack. It is an accumulated process. Once it reaches a limit, “StackOverflow” will happen. Stack Overflow is when we run out of memory to hold items in the stack. python have a default recursive limit  1000, but you can change it by calling sys.setrecursionlimit(num_of_limit)
Other than that, recursive is just much slower and slower. So if you are a game programmer, don’t ever use recursion :P
Additional Knowledge
The reason that why recursive slow
// TODO
Dynamic Programming(DP)
Dynamic Programming (from now on abbreviated as DP) is an optimization method for recursion. There is 2 way of doing DP. TopDown DP and BottomUp DP.
Example 1: Wedding Shopping
Problem statement:
Given different models for each garment (e.g. 3 shirts, 2 belts, 4 shoes, ...), buy one model of each garment. As the budget is limited, we cannot spend more money than the budget, but we want to spend the maximum possible. But it is also possible that we cannot buy one model of each garment due to that small amount of budget.
The input consists of two integers 1 ≤ M ≤ 200 and 1 ≤ C ≤ 20, where M is the budget and C is the number of garments that you have to buy. For a garment id ∈ [0... .C1], we know an integer 1 ≤ K ≤ 20 which indicates the number of different models for that garment id, followed by K integers indicating the price of each model ∈ [1... .K] of that garment id.
The output should consist of one integer that indicates the maximum amount of money necessary to buy one element of each garment. If there is no solution, print "No solution"
Example input 01
M = 20, C = 3
3 models of garment id 0 → 6 4 8
2 models of garment id 1 → 5 10
4 models of garment id 2 → 1 5 3 5
Example output 01
19
Exaplanation
(8 + 10 + 1)
8 from garment id 0
10 from garment id 2
1 from garment id 2
To do it in DP
shop(money_left, garment_id) is a notation of buying garment_id with money_left that you have
Method 1: Bruce Force
Do a complete search. You may do it in this way
if money_left < 0,
shop(money_left, garment_id) = INVALID
if a model from the last garment_id has been bought,
shop(money_left, garment_id) = M  money_left (this is the actual money spent)
in general case, for all model in [1 . . .K] of current garment_id
shop(money_left, garment_id) = max(shop(money_left  price[garment_id][model], garment_id + 1))
This solution just works! But it is very slow! Let’s take a look at a bigger range of input. Assume garment_id 0, 1, … 20. All of them have 20 choices. The time complexity will be 20 x 20 x … x 20 of total 20 times in the worst case. In the end, it will end up with O(20^{20})
This is where we come to method 2, doing it recursively with some optimization.
Method 2: TopDown DP(Memorization)
Memorization is one of the optimization technique for recursion. First, when we doing recursive or DP. We have to analyze the question and come out a subproblem, where usually they have.

This problem has optimal substructures (Criteria for using recursive). This is shown in Complete Search recurrence 3 above: solution for the subproblem is part of the solution of the original problem.

This problem has overlapping subproblems(Criteria of using TopDown DP). The search space is not as big as 20^{20} analyzed in Complete Search discussion above as many subproblems are overlapping. For instance, we repetitively compute some of the same subproblems.
Once the 2 criteria are satisfied. We can do it in TopDown DP!
Suppose that there are 2 models in certain garment_id with the same price p. Then, Complete Search will move to the same subproblem shop(money_left  p, garment_id + 1) after picking either model! Similarly, this situation still happen again if some combination of money_left and chosen model’s price causes money_left1  p1 = money_left2  p2. Then, the same subproblem will be computed more than once! Inefficient!
But how many subproblems is there for us to compute to get the answer? Assume, we have 201 money(0  200, inclusive), 20 possible garment_id(0  19, inclusive). Then to solve this problem, we only need to compute for 201 x 20 = 4020 subproblems. Easy? Yes.
How to do it?
Initialize a DP 'memo' table with the size of distinct subproblems
At the start of a recursive function, simply check if this current state has been computed before.
(a) If yes, return the value from the DP memo table, O(1).
(b) If not, compute and then store the computed value in the memo table, for future usage
If it has M states, then it requires at least O(M) memory space. If filling a 'memo' table requires O(k) steps, then the overall time complexity is O(kM). In the example above has M = 201 × 20 = 4020 and k = 20 (as we have to iterate through at most 20 models for each garment_id). Thus the time complexity is 4020 × 20 = 80400.
Method 3: BottomUp
I would say this method is one of the amazing power of DP. Step of doing this can be summarized as
1. Identify the Complete Search recurrence as with topdown DP above
2. Initialize some parts of the DP table with known initial values
3. Determine how to fill the rest of the DP table based on the Complete Search recurrence, usually involving one or more nested loops to do so
First, we have a boolean matrix can_reach[money_left][garment_id] of size 201 × 20, initialize it with False. And only the cells reachable by buying and of the models will be set as True. For example, ‘206=14’, ‘204=16’, ‘208=12’, that means only money with 14, 16, 12 are reachable in this case, so it will set as true. Also, can_reach[a + price of any model of the previous garment_id][b  1] only will be set as true. By doing this, only those cell that is ‘reachable’ in this problem will be computed. And in the end, the answer can be found in the last column. Find the cell in that column nearest to index 0 that is set to be true.
This means that we can somehow reach this state (money_left = 1) by buying a combination of various garment models. The final answer is M  money_left, or in this case, 201 = 19. The answer is “no solution” if there is no cell in the last column that is set to be true.
Example 2: Uber Interview Question  Maximum Sum of Nonadjacent Elements
Problem Statement:
Given an array of integers, find the subset of nonadjacent elements with the maximum sum. Calculate the sum of that subset.
Example input 01
3 7 4 6 5
Example output 01
13
The possible subset are [3 4 5],[3 4],[3 6], [3 5], [7 6], [7 5], [4 5]. Where sum of [7 6] is 13.
There are multiple ways of doing it
 Burce Force(Recursive)
 TopDown DP
 BottomUp DP
Method 1: Bruce Force The bruteforce approach will be to generate all subsets of elements of the array and for each subset where the elements are nonadjacent, then check the sum and print the maximum of all the sums. The timecomplexity of this approach is O(2^n). Which is pretty slow.
Method 2: TopDown DP
// TODO: not yet finished :P