Using dynamic programming
I am preparing interviews for software developers and trying to understand how to apply dynamic programming. I know that a problem must meet two criteria - have an optimal substructure and overlapping sub-problems. For an example where you have a function f (L) that takes a list of integers L and maps it to another integer (eg f ([17, 5, 2, 12] = 35), how would you apply dynamic programming to find the maximum value?
Example
L = [17, 5, 2, 12, 9]
You can have many combinations of f ():
f([17]) + f([5]) + f([2, 12, 19])
f([17]) + f([5, 2]) + f([12, 19])
I approached it by calculating f () for each element of the list, like f ([17]). Then each of two elements, such as f ([17, 5]), then each three elements of f ([5, 2, 12]), etc. Then I mapped these values into a hash table. Then I tried all combinations of f () to find the maximum value. I think this approach is neither graceful nor awkward. Any ideas on how to approach?
source to share
The typical dynamic programming way is to create a function that recursively goes through all the allowed permutations of subproblems to give the final answer, and preserves all the answers to the subproblems as we go (called memoization), since these submasters are likely to be very reusable. In pseudocode for an example problem:
function F(some_list) {
....
}
M = [[]]
L = [17, 5, 2, 12, 9]
function maximize(start, end) {
// If we have already calculated the highest value
// for the given slice, why do it again?
if (M[start][end] != NULL) {
return M[start][end]
}
// The function f applied to the whole slice we are
// examining is also a viable solution, so we start
// our hunt there
max = F(L.slice(start, end))
// If we are at an end node (that is, we can't
// divide the problem into smaller pieces) we return
// and save the value we just calculated
if (end - start == 1) {
M[start][end] = max
return max
}
// Let look at all possible ways we can split the
// slice we are currently examining
for (split in range(start + 1, end - 1)) {
// Let examine booth parts of the slice and see if
// the sum of those solutions are better than our
// previous best solution
temp_max = maximize(start, split) + maximize(split, end)
if (temp_max > max) {
max = temp_max
}
}
// We have examined all possible ways in which we can
// slice and dice our slice, and found the best
// solution. Yay! Let save it for future reference.
M[start][end] = max
return max
}
// Examine the whole list
the_great_maximum_value = maximize(0, L.length)
source to share
Here's one possible way to do it:
1) Define dp[pos]
as the maximum value that can be obtained by breaking the first pos
elements of the list somehow (no matter how).
2) Base Register: dp[0] = 0
. This is the case for an empty prefix.
3) for pos > 0
:
dp[pos] = max(dp[prev_pos] + f(L[prev_pos + 1], L[prev_pos + 2], ..., L[pos]))
for 0 <= prev_pos < pos
.
4) Answer dp[length(L)]
.
Time complexity O(n^2 * time_to_comptute_f)
(because we iterate over all the positions in the list and for each position we check the O(n)
previous positions, calculating f
each time).
Complexity of space O(n)
.
source to share