Dynamic Programming
See all coding puzzles and patterns here.
Algorithm Description
Dynamic programming is a programming technique wherein a larger problem is broken down into a smaller subproblem plus a computation for the remainder of the problem.
DP algorithms generally construct a solution vector, which can be multidimensional, starting with a base case
and then building on that base case up toward the solution.
Once the target solution is constructed, it is returned.
The solution vector is generally called dp.
Example
For example, to solve the unbounded knapsack problem, we construct a solution vector dp of length
t equal to the target sum, where dp[i] indicates the number of ways that i can be
constructed using a sum of any of the available numbers.
We start with the base case dp[0] = 1 because 0 can be constructed in only one way, by using none of the elements.
Next we iterate over each element i in dp to compute the new j that can be
attained by adding each number in the available numbers to i.
If dp[i] is equal to 0, then we skip any additions because i cannot be attained,
implying that no sums can be constructed with i as the base.
For each number that can be attained, we add dp[i] to the existing value at dp[j].
The iteration over the dp is continued until the target sum t is computed in dp[t].
If we have a target of 10 and available numbers 2 and 4, and we want to know the number of ways 10 can be constructed as a sum of the available numbers, then the construction will look like:
setup: dp = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i = 0: dp = [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
i = 1: dp = [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
i = 2: dp = [1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0]
i = 3: dp = [1, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0]
i = 4: dp = [1, 0, 1, 0, 2, 0, 3, 0, 2, 0, 0]
i = 5: dp = [1, 0, 1, 0, 2, 0, 3, 0, 2, 0, 0]
i = 6: dp = [1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 3]
i = 7: dp = [1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 3]
i = 8: dp = [1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8]
i = 9: dp = [1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8]
The total permutations of 2 and 4 that can sum to 10 are:
2 + 2 + 2 + 2 + 2
2 + 2 + 2 + 4
2 + 4 + 4
2 + 2 + 4 + 2
2 + 4 + 2 + 2
4 + 2 + 2 + 2
4 + 2 + 4
4 + 4 + 2
If wanted to know the combinations adding to the target (i.e., only 2 + 2 + 2 + 2 + 2,
2 + 2 + 2 + 4 and 2 + 4 + 4) then we should store each combination as a set at each location
instead of just the number of permutations that add to that number.
In such a solution, we would initialize dp with every element set to an empty array, which would be
equivalent to a value of 0 in the permutations solution above, and then set dp[0] to an array
containing the empty set, which would be equivalent to the value 1 in the permutations solution above.
We would then add the newest element to the existing sets at each i and append the new set to the existing
array at the new sum.
The sequence would then be:
setup: dp = [[()], [], [], [], [], [], [], [], [], [], []]
i = 0: dp = [[()], [], [(2)], [], [(4)], [], [], [], [], [], []]
i = 1: dp = [[()], [], [(2)], [], [(4)], [], [], [], [], [], []]
i = 2: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2)], [], [], [], []]
i = 3: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2)], [], [], [], []]
i = 4: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2), (2, 2, 2)], [], [(4, 4)], [], []]
i = 5: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2), (2, 2, 2)], [], [(4, 4)], [], []]
i = 6: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2), (2, 2, 2)], [], [(4, 4), (4, 2, 2), (2, 2, 2, 2)], [], []]
i = 7: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2), (2, 2, 2)], [], [(4, 4), (4, 2, 2), (2, 2, 2, 2)], [], []]
i = 8: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2), (2, 2, 2)], [], [(4, 4), (4, 2, 2), (2, 2, 2, 2)], [], [(4, 4, 2), (4, 2, 2, 2), (2, 2, 2, 2, 2)]]
i = 9: dp = [[()], [], [(2)], [], [(4), (2, 2)], [], [(4, 2), (2, 2, 2)], [], [(4, 4), (4, 2, 2), (2, 2, 2, 2)], [], [(4, 4, 2), (4, 2, 2, 2), (2, 2, 2, 2, 2)]]
Puzzles
| Puzzle | Difficulty | External Link |
| 0-1 Knapsack | Medium | |
| Biggest Square in City Skyline | Medium | |
| Distinct Subsequences | Medium | |
| Find Number of Palindromic Substrings in a String | Medium | |
| Longest Common Subsequence | Medium | Leetcode 1143 |
| Longest Common Substring | Medium | |
| Longest Increasing Subsequence | Medium | Leetcode 300 |
| Sums from Weighted Words | Medium |
