Dynamic Programming ( A Magic 😵 )

Now, the time has come to dirt your hand with so called "DP".

DP ≈ careful brute force

DP ≈ guessing + recursion + memoization

DP ≈ shortest path in some DAG( directed acyclic graph )

time = #subproblems * ( time / subproblem )

DP is an algorithmic technique that is usually based on a recurrent formula and one(some) starting state.

State: It is a way to describe the situation, a sub-solution of the problem.

5 easy steps to DP

• define subproblems
• guess
• relate subproblem solution
• recurse & memoization( Top-down ) OR build DP table ( Bottom-up )
• solve the original problem

How to choose subproblems

• suffixes x[i:] ⩝ i     O(n)
• prefixes x[i:] ⩝ i     O(n)
• substrings x[i:j] ⩝ i ⪯ j    O(n*n)

Time complexity

The running time of the dynamic programming algorithm depends on the product of two factors:

• The number of overall subproblems. 
• How many choices we look for each subproblem.