Hexbyte News Computers

Dynamic programming (DP, as I’ll refer to it here on) is a toughie.

I’ve heard a lot of friends and juniors complain about dynamic programming and about how non-intuitive it is.

Plus, problems on DP are pretty standard in most product-company-based hiring challenges, so it seems like a good topic to address on a blog based on algorithms.

Here’s a heads-up to you though, since this article is the first in (maybe, depending on its reception), a multi-part series on DP, this article will focus on setting the groundwork of DP and I’ll dedicate most of this article to explaining how to arrive at the solutions to classical DP problems, and the general pattern of thought that I use when it comes to DP.

This article, I’ll be tackling the following –

- Coin Change Problem
- 0-1 Knapsack Problem
- DP on grids

And I’ll be leaving some more classical variants of DP as exercises.

If you’re already fully confident of why/how the above DP algorithms work correctly, then reading this article may yield little value, and you may be better off waiting for the next article on DP. 🙂

Should I add future articles, I’ll tackle some non-classical variants of DP, leveraging intuition and logic.

Onto the article!

### DP: An Intro

I’ve found myself solving the nicest of DP questions when I leverage recursion.

This is something I’ve often noticed in general, that for me, recursion is very intuitive.

While DP at times does seem confusing, I’ve found from personal experience that thinking of solutions and problems recursively makes reaching a DP solution that much easier.

Let’s take an example –

##### The Coin Change Problem

Let’s say you have an infinite amount of `K`

different denominations of coins.

You need to find the minimum number of coins to possess a value of N dollars.

For example, if `K = 2`

and your denominations are `{1, 2}`

, and you want to find the min. number of coins needed to generate `N=9`

dollars.

Here, it’s pretty obvious that’d be `5`

coins (`4`

two dollar coins + `1`

one dollar coin).

Note: A greedy algorithm of selecting the largest available denomination under

`N`

at every instant won’t give optimal answers.Try out the test case:

`K=3`

,`denominations = {1, 3, 4}`

and`N = 10`

.The greedy answer yields 4 coins (

`4`

+`4`

+`1`

+`1`

) while the optimal answer is 3 coins (`4`

+`3`

+`3`

).

Thus, clearly we need to check all possible coin selections we can make.

Now let’s model the problem recursively.

Let’s define a mathematical function `f`

where `f(N)`

tells me the minimum number of coins I need to generate a value of `N`

.

Let’s say I have `K`

denominations.

Now, if I were to take away a coin from my value of `N`

, this coin could be of any denomination, correct?

Basically, `N`

could be re-written as `((N-denom[i]) + denom[i])`

for any valid `0<=i`

`I also know, that `

`denom[i]`

can be represented as 1 coin (a coin whose value equals `denom[i]`

).

`Thus, `

`f(N) = f(N-denom[i]) + 1`

`This is our general case.`

`What’s our base case?`

`If `

`N=0`

, we need 0 coins.

`Similarly, if `

`N<0`

, its an impossible case, which needs to be handled.

`Compiling all this, we have:`

```
>>> def f(n, denom):
ans = 10**10
if n<=0:
return 0
for i in denom:
if n-i>=0:
ans = min(ans, 1+f(n-i, denom))
return ans
>>> f(10, [1,3,4])
3
```

`Yay!`

`Now there are a couple of things we need to ensure we’re handling, if we want to port this to DP.`

`No global variables should be modifed in the function`

`Simple, memorizable states (state-space reduction)`

`And… I’d say that’s it?`

`Now, we can make `

`denom`

a global array as we’re not changing it.

`This makes our function just have one parameter. The current value, `

`N`

.

`Thus, we have an O(N*K) DP solution to this, as follows -`

```
>>> dp = [-1 for i in range(n)]
>>> def f(n):
if dp[n]!=-1:
return dp[n]
ans = 10**10
if n<=0:
return 0
for i in denom:
if n-i>=0:
ans = min(ans, 1+f(n-i))
dp[n] = ans
return ans
```

`And that’s it!`

`The 0-1 Knapsack Problem`

`Okay, so let’s say you’re a burglar who has a bag (knapsack) that can carry a total weight of `

`W`

.

`There are `

`N`

valuable objects in the house you broke into.

`Each object `

`i`

, has a weight of `wt[i]`

and a value of `vals[i]`

.

`Your task as a burglar is to devise an efficient algorithm that can maximize the net value of objects you can steal from the house provided you place them all in your knapsack.`

`I hope you don’t have to apply this in seriousness. 😛`

`So, let’s think recursively here.`

`In general, whenever problems involve multiple solutions where there’s an “option” to choose or ignore an element, I find it suitable to use the current index of the element as a parameter.`

`So this means that my `

`f()`

method already has one parameter - `int idx`

`Now let’s think about what our other parameter could be by simulating our burglary.`

`At any point, when we’re looking at the object at index `

`idx`

, we have a choice - to take it, or to not take it.

`The point of DP is to optimize our solution of “checking all possibilities”, without repeating checking already checked possibilities, right?`

`So, we have a choice – take the current object, or ignore it.`

`But let’s say we do take it – we still need to verify if our knapsack can hold it, right?`

`Lets look at this recursively.`

`To make sure our current possibility is valid, and to provide insight into our decision as to whether or not can we afford to take the next object, we NEED to know our current knapsack capacity that’s left.`

`So, our states are (current_index, weight_left).`

`Let’s see how we can model this as a recursive equation now -`

```
f(current_index, weight_left) = max( f(current_index + 1, weight_left), vals[current_index] + f(current_index+1, weight_left - wt[current_index]) )
```

`Look closely to the right-hand-side of that equation.`

`We’re stating:`

`f(idx, weight) = max( possibility where we don’t take current element, possibility where we do take current element )`

`It’s important to note that we’ve defined `

`f(idx, weight)`

to be the maximum value we can obtain assuming we’re at index `idx`

with weight `weight`

left over.

`Also, pay attention to the states in the latter possibility, we even update the `

`weight_lef`