[Algorithms][DP] Dynamic Programming Explaiend

Dynamic Programming (DP) is a technique of solving a problem that depends on a smaller instance of a smaller problem

When DP can be applied:
0. If the best solution of the larger problem can be computed from the best solution of the smaller problem(s). This property is called optimal substructure property.  If you can formulate a recursive equation such as f(n) = f(n-1) + f(n-2), you can solve the bigger problem f(n) with the result from smaller problems, which means the problem shows optimal substructure property. To know if the optimal substructure property exists or not ask the following -
"Can I solve the problem recursively?"

1. DP can be applied on the problems that shows overlapping sub problems. For instance, fibonacci(n) = fibonacci(n-1) + fibonacci(n-2). Lets see the tree structure of this problem,
                                                  f(n)
                                                 /    \
                                           f(n-1)   f(n-2)
                                            /     \         /   \
                                     f(n-2)    f(n-3) .......................

From the tree above, we can see that f(n-2) appears twice. To find if there is overlapping sub-problem property or not ask the following question-
"Am I solving the same problem more than once?"


In short, to check if DP can be applied on a given problem or not, see at first if it can be solved recursively, then see in the recursion tree if any sub-problem is occurring more than once.

Steps on formulating a problem using DP
Lets consider the problem of finding the shortest path in a graph.
0. Find variables that express the problem. To find shortest path, we need a vertex to start from (u) and a vertex we want to reach (v). For this problem u and v are the minimum number of variables to express the problem at hand. DP(u, v) would be state of the problem we want to compute.
1. Find relationship of the main problem with sub-problem states.
DP(u, v) = min(DP(u, k) + DP(k, v)) for all k
3. Build table to memorize sub problem's solutions.

Determining Order of a DP problem
0. Find the total number of sub-problems (s). For the shortest path problem, u would take all possible vertices. So, s = |V|
1. Determine how much work is done to compute a problem (w). Order of a recursive call to a sub-problem would be constant, as for DP it will be only a table look up, so for the shortest path problem,  DP(u, k) + DP(k, v) takes constant time.  We need to iterate through all k reachable from u, so w = degree(u).
3. Runt time, O(DP(u, v)) = s * w = O(|V| + |E|)

Reference:
0. MIT OCW
1. GeeksforGeeks
2. Dr. Fuentes' lecture
3.