CODEWITHSUNDEEP
algorithmdynamic-programming
MNRC
MNRC

Reputation: 175

Application of dynamic programming

I'm prepping for software developer interviews and trying to understand how to apply dynamic programming. I know that a problem must meet two criteria--have an optimal substructure and overlapping subproblems. Given 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 a variety of 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, such as f([17]). Then each two elements, such as f([17, 5]), then each three elements, f([5, 2, 12]), and so on. I then mapped these values to a hash table. Next, I tried all the combinations of f() to find the maximum value. I think this approach is not elegant and kind of awkward. Any ideas for how to approach?

Upvotes: 3

Views: 465

Answers (2)

Fors
Fors

Reputation: 186

A typical way to go about dynamic programming is to create a function that recursively goes through all valid permutations of the subproblems in order to give the final answer, and saving all the answers to the subproblems as you go along (which is called memoization), as those subanswers will probably be very reusable. In pseudo code for the 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's look at all possible ways we can split the
    // slice we are currently examining
    for (split in range(start + 1, end - 1)) {
        // Let's 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's save it for future reference.
    M[start][end] = max
    return max
}

// Examine the whole list
the_great_maximum_value = maximize(0, L.length)

Upvotes: 3

kraskevich
kraskevich

Reputation: 18576

Here is one possible way to do it:

1)Let's define dp[pos] as a maximum value that can be obtained by splitting the first pos elements of the list somehow(no matter how).

2)Base case: dp[0] = 0. That 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)The answer the dp[length(L)].

Time complexity is O(n^2 * time_to_comptute_f)(because we iterate over all positions in the list and for each position check O(n) previous positions, computing f every time).

Space complexity is O(n).

Upvotes: 1

Related Questions