Understanding dynamic programming and memoization

yourbasic.org

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

Chocolate feast 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.

Problem partly solved

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 solution

// 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.

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 < jn, 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
    }

    day := 1 + len(choco) - (j - i)
    if j-i == 1 {
        return day * choco[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

Share this page: