If you haven't already, go watch the video Mastering Dynamic Programming by Tech With Nikola! This tutorial is based off that.

We will look into three examples today, and gain some new insights by visualizing the call trees.

- Fibonacci
- Minimum Coins
- Longest common subsequence

## Fibonacciโ

This one is tried and true! But not bad as a starter:

`fn fib(n: i32) -> i32 {`

if n <= 2 {

return 1;

}

fire::dbg!("return", fib(n - 1) + fib(n - 2))

}

What does the call tree of `fib(5)`

look like?

Call tree of `fib(5)` |

To make it more efficient, we can use a "memo" to cache the function calls. There are multiple ways to do this, let's try using a static `HashMap`

:

`lazy_static::lazy_static! {`

static ref MEMO: Mutex<HashMap<i32, i32>> = Mutex::new(HashMap::new());

}

fn fibm(n: i32) -> i32 {

if n <= 2 {

return 1;

}

{

let mut memo = MEMO.lock().unwrap();

if let Some(o) = memo.get(&n) {

return *o;

}

// we have to release the lock here

}

let res = fibm(n - 1) + fibm(n - 2);

let mut memo = MEMO.lock().unwrap();

memo.insert(n, res);

res

}

Now, what will the call tree look like?

Call tree of `fibm(5)` |

Nice! We can see that the `fibm(n = 3)`

(9th node) returned early.

Here is one more comparison for `fib(10)`

.

Call tree of `fib(10)` |

Call tree of `fibm(10)` |

We can see that the memo helped reduce the number of nodes down from 111 to just 19!

## Minimum Coinsโ

Let's get to a slightly more interesting problem. According to Wikipedia, the change-making problem addresses the question of finding the minimum number of coins that add up to a given amount of money.

Example 1:

Given the coins `{ 1, 2 }`

(with unlimited number), how many coins do we need to make up to `5`

?

The answer is 3, with coins `1`

+ `2`

+ `2`

. Now, let's look at the standard recursive implementation:

`fn min_coins(m: i32, coins: &[i32]) -> Option<usize> {`

if m == 0 {

return Some(0);

}

let mut count: Option<usize> = None;

for coin in coins {

let next = m - coin;

if next < 0 {

continue;

}

count = match (count, min_coins(next, coins)) {

(Some(a), Some(b)) => Some(a.min(b + 1)),

(Some(a), None) => Some(a),

(None, Some(b)) => Some(b + 1),

(None, None) => None,

}

}

fire::dbg!("return", count)

}

The call tree for `min_coins(13, &[1, 4, 5])`

:

Call tree of `min_coins(13, ..)` |

With memoization, we'd use a context specific `HashMap`

:

`fn min_coins_m(m: i32, coins: &[i32], memo: &mut HashMap<i32, Option<usize>>) -> Option<usize> {`

if m == 0 {

return Some(0);

}

if let Some(c) = memo.get(&m) {

return *c;

}

let mut count: Option<usize> = None;

for coin in coins {

let next = m - coin;

if next < 0 {

continue;

}

count = match (count, min_coins_m(next, coins, memo)) {

(Some(a), Some(b)) => Some(a.min(b + 1)),

(Some(a), None) => Some(a),

(None, Some(b)) => Some(b + 1),

(None, None) => None,

}

}

memo.insert(m, count);

count

}

Now, the call tree is reduced down to just 28 nodes:

Call tree of `min_coins_m(13, ..)` |

Not bad, right?

## Longest common subsequenceโ

This is the most interesting and practical problem. The video uses it to implement a git diff algorithm which is pretty neat.

Here let's go straight into memoizing, because otherwise it would never return even for trivial test cases:

`struct Memo {`

memo: HashMap<(usize, usize), usize>,

}

fn lcs_impl<T: Copy + Eq>(left: &[T], right: &[T], state: &mut Memo) -> usize {

if left.is_empty() || right.is_empty() {

return 0;

}

fire::dbg!("(i, j)", (left.len() - 1, right.len() - 1));

if let Some(n) = state.memo.get(&(left.len() - 1, right.len() - 1)) {

return *n;

}

let n = if left[left.len() - 1] == right[right.len() - 1] {

1 + lcs_impl(&left[..left.len() - 1], &right[..right.len() - 1], state)

} else {

let leftn = lcs_impl(&left[..left.len() - 1], right, state);

let rightn = lcs_impl(left, &right[..right.len() - 1], state);

leftn.max(rightn)

};

state.memo.insert((left.len() - 1, right.len() - 1), n);

n

}

The `.len() - 1`

bits are pretty verbose, but if you look pass them, the code should be pretty understandable. The clever bit here is to use a `HashMap`

with a tuple key instead of a 2D vector to save space!

But it's only half of the story. Because we still need to walk the path again to re-construct the common subsequence:

`pub fn lcs<T: Copy + Eq>(left: &[T], right: &[T]) -> Vec<T> {`

let mut state = Memo {

memo: Default::default(),

};

let length = lcs_impl(left, right, &mut state);

// reconstruct the common subsequence

let mut seq = Vec::new();

let (mut i, mut j) = (left.len() - 1, right.len() - 1);

while seq.len() < length {

if left[i] == right[j] {

seq.push(left[i]);

if seq.len() == length {

break;

}

i -= 1;

j -= 1;

} else {

if i > 0 && state.memo.get(&(i, j)).unwrap() == state.memo.get(&(i - 1, j)).unwrap() {

i -= 1;

} else {

j -= 1;

}

}

}

seq.reverse();

seq

}

Here is the call tree for:

`assert_eq!(`

lcs(&[1, 4, 5, 6, 9, 10, 11], &[6, 4, 5, 9, 11]),

[4, 5, 9, 11]

);

Call tree of `lcs(..)` |

Memo of `lcs(..)` (last node) |

If we look into the memo of the last node, we can see that we only used 13 elements, instead of 8 x 6 = 48 as in the video (or pretty much every other tutorial), and that the call tree only has 35 nodes. So there is some trade-off between top-down vs bottom-up dynamic programming here.

## Conclusionโ

I hope you learnt something today! FireDBG is your *best companion* in writing, debugging and analyzing algorithms. You don't have to install the Rust toolchain to interact with the call trees, as I have bundled them in the testbench with full source code here. You should be able to just open the `dynamic-programming`

folder, install the VS Code extension and start playing.