LESSON 44/53Algorithm Techniques

Dynamic Programming

GOALRemember repeated work instead of doing it again.

Computing Fibonacci by plain recursion, f(30) makes over 1.6 million calls — because it works out the same values again and again. Store each answer in an array and look it up next time, and it becomes 30 calls. That single idea is all dynamic programming is.

ON THIS PAGE

The example
Line by line
Watch it run
Top-down and bottom-up
Recognising a DP problem
Common mistakes
Key words
Quick check
Now you try

SHOW EXAMPLE IN

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<long long> memo;
long long calls = 0;

long long fib(int n) {
    calls++;
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    memo.assign(31, -1);
    cout << fib(30) << endl;
    cout << calls << endl;
    return 0;
}

> what you see

832040
59

Try this code

//LINE BY LINE

memo.assign(31, -1);

-1 means "not worked out yet". Fibonacci values are never negative, so it is a safe marker.

if (memo[n] != -1) return memo[n];

Already known, so return it. This ONE line turns 1.6 million calls into 59.

memo[n] = fib(n - 1) + fib(n - 2);

Work it out and STORE it. Forget the storing and the gain vanishes.

vector<long long> memo;

long long because Fibonacci grows fast — f(47) already overflows an int.

Watch it run

fib(5) calls fib(4) and fib(3). Those split again in turn.

1 / 6

Top-down and bottom-up

Dynamic programming is written two ways. They do the same work; only the shape on the page differs.

	Top-down (memo)	Bottom-up (table)
Хэлбэр / Looks like	Рекурс + санах ой / recursion plus a cache	Давталт + массив / a loop filling an array
Бичихэд / To write	Амархан / easier	Бодох шаардлагатай / needs more thought
Хурд / Speed	Арай удаан / slightly slower	Хурдан / faster
Эрсдэл / Risk	Стек дүүрэх / stack overflow	Дараалал буруу / filling in the wrong order

Write the plain recursion first, check it works, then add the memo. Speeding up something correct is much easier than starting from an empty table.

Recognising a DP problem

Two properties have to hold together. One on its own is not enough.

1.Overlapping subproblems: the same smaller problem comes up many times.
2.Optimal substructure: the answer to the big problem is built from the answers to smaller ones.

Without the first property a memo is wasted — nothing is ever looked up twice. Then plain recursion or backtracking is what you want.

//COMMON MISTAKES

✗ wrong

memo-г 0-ээр дүүргэх / Filling the memo with 0

✓ right

-1 гэх мэт боломжгүй утгаар / Use an impossible value like -1

0 can be a real answer, so you can no longer tell "known" from "unknown".

✗ wrong

Хадгалаад буцаахаа мартах / Storing but forgetting to return

✓ right

return memo[n];

Storing without returning leaves the function handing back rubbish.

//KEY WORDS

memoization

Remembering an answer you already worked out.

overlapping subproblems

The same smaller problem coming up many times. The condition DP needs.

//QUICK CHECK

What does memoising actually change?

//NOW YOU TRY

Compute fib(30) without the memo and count the calls. Then add the memo and compare.

Open editor

Backtracking One-dimensional DP

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<long long> memo;
long long calls = 0;

long long fib(int n) {
    calls++;
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    memo.assign(31, -1);
    cout << fib(30) << endl;
    cout << calls << endl;
    return 0;
}

> what you see

832040
59

Try this code

//LINE BY LINE

memo.assign(31, -1);

-1 means "not worked out yet". Fibonacci values are never negative, so it is a safe marker.

if (memo[n] != -1) return memo[n];

Already known, so return it. This ONE line turns 1.6 million calls into 59.

memo[n] = fib(n - 1) + fib(n - 2);

Work it out and STORE it. Forget the storing and the gain vanishes.

vector<long long> memo;

long long because Fibonacci grows fast — f(47) already overflows an int.

Top-down and bottom-up

Dynamic programming is written two ways. They do the same work; only the shape on the page differs.

	Top-down (memo)	Bottom-up (table)
Хэлбэр / Looks like	Рекурс + санах ой / recursion plus a cache	Давталт + массив / a loop filling an array
Бичихэд / To write	Амархан / easier	Бодох шаардлагатай / needs more thought
Хурд / Speed	Арай удаан / slightly slower	Хурдан / faster
Эрсдэл / Risk	Стек дүүрэх / stack overflow	Дараалал буруу / filling in the wrong order

Write the plain recursion first, check it works, then add the memo. Speeding up something correct is much easier than starting from an empty table.

Recognising a DP problem

Two properties have to hold together. One on its own is not enough.

1.Overlapping subproblems: the same smaller problem comes up many times.
2.Optimal substructure: the answer to the big problem is built from the answers to smaller ones.

Without the first property a memo is wasted — nothing is ever looked up twice. Then plain recursion or backtracking is what you want.

//COMMON MISTAKES

✗ wrong

memo-г 0-ээр дүүргэх / Filling the memo with 0

✓ right

-1 гэх мэт боломжгүй утгаар / Use an impossible value like -1

0 can be a real answer, so you can no longer tell "known" from "unknown".

✗ wrong

Хадгалаад буцаахаа мартах / Storing but forgetting to return

✓ right

return memo[n];

Storing without returning leaves the function handing back rubbish.

//QUICK CHECK

What does memoising actually change?