# Dynamic programming [step-by-step example]

- Problem
- Recursive algorithm
- Dynamic programming with memoization
- Dynamic programming with tabulation
- Memoization vs. tabulation

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(n^{2}) 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.