Dynamic programming [step-by-step example]

This text contains a detailed example showing how to solve a tricky problem efficiently with recursion and dynamic programming – either with memoization or tabulation.

• A dynamic programming algorithm solves a complex problem by dividing it into simpler subproblems, solving each of those just once, and storing their solutions.
• Memoization is an optimization technique used to speed up programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
• Tabulation is an approach where you solve a dynamic programming problem by first filling up a table, and then compute the solution to the original problem based on the results in this table.

Problem

You’ve just got a tube of delicious chocolates and plan to eat one piece a day – either by picking the one on the left or the right.

Each piece has a positive integer that indicates how tasty it is. Since taste is subjective, there is also an expectancy factor. A piece will taste better if you eat it later: if the taste is m (as in hmm) on the first day, it will be km on day number k.

Your task is to design an efficient algorithm that computes an optimal chocolate eating strategy and tells you how much pleasure to expect.

Recursive algorithm

// Joy returns the total pleasure if you eat the chocolates
// in an optimal order starting at the given day.
func Joy(choco []int, day int) int {
    n := len(choco)
    if n == 1 {
        return day * choco[0]
    }
    left := day*choco[0] + Joy(choco[1:], day+1)
    right := day*choco[n-1] + Joy(choco[:n-1], day+1)
    return max(left, right)
}

Note that the function solve a slightly more general problem than the one stated. It computes the total pleasure if you start eating at a given day. This is a common strategy when writing recursive code.

It’s easy to see that the code gives the correct result.

• In the base case, where choco contains only one element, the function returns the correct value.
• When choco contains n elements, n > 1, we have to start with either choco[0] or choco[n-1]. The code computes the pleasure for each of these cases with recursion, and returns the maximum.

Dynamic programming with memoization

The code above is simple but terribly inefficient – it has exponential time complexity.

However, many or the recursive calls perform the very same computation. In fact, the only values that need to be computed are

joy(choco[i:j], day)

where 0 ≤ i < j ≤ n, day = 1 + n - (j - i) and n = len(choco).

The joy of choco[i:j] is either computed directly (the base case), or it can be computed in constant time from the already known joy of choco[i+1:j] and choco[i:j-1]. If we use dynamic programming and memorize all of these subresults, we will get an algorithm with O(n2) time complexity.

To implement this strategy using memoization we need to include the two indexes in the function call. To help record an optimal solution, we also keep track of which choices (left or right) that gives optimal pleasure.

type result struct {
    joy      int
    pickLeft bool
}

// JoyMemo returns the joy if you eat the chocolates choco[i:j]
// in an optimal order starting at day 1 + len(choco) - (j - i).
func JoyMemo(choco []int, i, j int, memo [][]result) int {
    // Reuse previous result, if available.
    if res := memo[i][j].joy; res != 0 {
        return res
    }
    // base case
    if j-i == 1 {
        return len(choco) * choco[i]
    }
    // recursion
    day := 1 + len(choco) - (j - i)
    left := day*choco[i] + JoyMemo(choco, i+1, j, memo)
    right := day*choco[j-1] + JoyMemo(choco, i, j-1, memo)
    res := max(left, right)
    // Save the result.
    memo[i][j].joy = res
    memo[i][j].pickLeft = left > right
    return res
}

Given the memo table, it’s a simple matter to print an optimal eating order:

for i, j := 0, n; i < j; {
    if memo[i][j].pickLeft {
        fmt.Print("left ")
        i++
    } else {
        fmt.Print("right ")
        j--
    }
}

Complete code: chocolate.go

Dynamic programming with tabulation

As an alternative, we can use tabulation and start by filling up the memo table. Note that the order of computation matters: to compute the value memo[i][j], the values of memo[i+1][j] and memo[i][j-1] must first be known.

// JoyTab returns a table containing the joys memo[i,j] that
// you get if you eat the chocolates choco[i:j] in an optimal
// order starting at day 1 + len(choco) - (j - i).
func JoyTab(choco []int) (memo [][]result) {
    n := len(choco)
    memo = make([][]result, n)
    for i := range memo {
        memo[i] = make([]result, n+1)
    }
    for i := range memo { // base cases
        memo[i][i+1].joy = n * choco[i]
    }
    for i := n - 1; i >= 0; i-- {
        for j := i + 2; j <= n; j++ {
            day := 1 + n - (j - i)
            left := day*choco[i] + memo[i+1][j].joy
            right := day*choco[j-1] + memo[i][j-1].joy
            memo[i][j].joy = max(left, right)
            memo[i][j].pickLeft = left > right
        }
    }
    return
}

Given this table, the optimal eating order can be computed exactly as before.

Complete code: chocolatetab.go

Memoization vs. tabulation

The choice between memoization and tabulation is mostly a matter of taste. However, if some subproblems need not be solved at all, memoization may be more efficient since only the computations needed are carried out.

Share: