# Understanding dynamic programming and memoization

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

**Dynamic programming**is a method for solving 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.

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

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.

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