Dynamic programing combines the correctness of complete search and the efficiency of greedy algorithms. There are three elements in Dynamic Programing.
- Optimal substructure: optimal solutions to current problem can be computed from its subproblems.
- Overlapping subproblems: same subproblem is solved multiple times.
- No aftereffect property: a subproblem that has been solved will not be affected by future decisions.
This set of algorithms highly depend on the actual question. Check the book for examples.
- Coin problem
- Question: Form a target sum by using minimal number of coins
- State transition function: MinNum[x] = min(MinNum[x-c]+1) for c in all coins
- longest increasing subsequence
- Question: Find the longest subsequence (not adjacent) that is increasing
- State transition function: SeqLenEndAt[i] = max(SeqLenEndAt[j]+1) for all array[j]< array[i]
- Paths in a grid
- Question: Find number of paths from source to destination, only allow specific move direction
- State transition function: PathNum[cur] = sum(PathNum[prev]) for all prev nodes lead to cur node
- Knapsack problems
- Question1: Knapsack capacity W. Each object weighs wi and values vi. Find the max values.
- State transition function1: DP[i][w] = max(MaxValueByObj[i-1][w-wi]+vi) for all objects and w. DP[i][w] means the max value by using first i objects and w capacity of the bag
- Question2: Each object can be chosen for infinite times
- State transition function2: DP[i][w] = max(MaxValueByObj[i-1][w-k*wi]+k*vi) = max(MaxValueByObj[i][w-wi]+vi)
- Question3: Each object can only be chosen for ki times
- State transition function3: DP[i][w] = max(MaxValueByObj[i-1][w-k*wi]+k*vi) for k from 0 to ki.
- Stock problem
- Question: Find the max profit by make k transaction on stock
- State transition function: MaxProfit[k][i] = max(MaxProfit[k][i-1], max(MaxProfit[k-1][j]+p[i]-p[j]) for j<i) for i from 0-th day to n-th day.
- Counting tilings
- Question: Count the ways of using 2*1 bricks to tile a rectangle.
- State transition function: According to how the previous row is cover, you can calculate ways that can cover the current row.
Common Optimization techniques
- Memorization: you can store the sub problem solution for future look up
- Dimension compression: you can remove some unused dimension of the DP array