What is dp problem
DP problem is a programming strategy which use extra space to save time. These problems need to store some state instead of calculate again. For most situation, DP is a strategy to reduce the time consuming for recursive problem.
- Memorization
- Tabulation
fibonacci example
The classic recursive problem:
1
2
3
4
| const fib = (n) => {
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
};
|
How to memorize :
1
2
3
4
5
6
7
| const fibMemo = (n, memo) => {
const key = n;
if (memo[key]) return memo[key];
if (n <= 2) return 1;
memo[key] = fib(n - 1) + fib(n - 2);
return memo[key];
};
|
How to tabulation:
1
2
3
4
5
6
7
8
9
10
| const fibTable = (n) => {
const table = Array(n + 1).fill(0);
table[1] = 1;
for (let i = 0; i <= n; ++i) {
table[i + 1] += table[i];
table[i + 2] += table[i];
}
return table[n];
};
|
Memorization Recipe
- Make it work
- visualize the problem as a tree
- implement the tree using recursion
- test it
- Make it efficient
- add memo object
- add a base case to return memo value
- store return values into the memo
Tabulation Recipe
- visualize the problem as table
- size the table base on inputs
- initialize the table with default values
- seed the trivial answer into the table
- iterate through the table
- fill further position based on the current position
What kind of question is dp
- Can the result be exist →→ True or False
- How the result be come →→ One result
- What is the best result →→ One of a best result
- What is all results (may not be dp problem) →→ all results
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| const canSum = (target, numbers, memo) => {
const key = target;
if (key in memo) return memo[key];
if (target === 0) return true;
if (target < 0) return false;
for (let num of numbers) {
let tmp = target - num;
if (canSum(tmp, numbers, memo)) {
memo[key] = true;
return memo[key];
}
}
memo[key] = false;
return memo[key];
};
let res = canSum(300, [25], {});
res;
const howSum = (target, numbers, memo) => {
const key = target;
if (key in memo) return memo[key];
if (target === 0) return [];
if (target < 0) return null;
for (let num of numbers) {
let tmp = target - num;
let sumRes = howSum(tmp, numbers, memo);
if (sumRes !== null) {
memo[key] = [num, ...sumRes];
return memo[key];
}
}
return null;
};
res = howSum(300, [7, 15], {});
res;
const bestSum = (target, numbers, memo) => {
const key = target;
if (key in memo) return memo[key];
if (target === 0) return [];
if (target < 0) return null;
let shortestRes = null;
for (let num of numbers) {
let tmp = target - num;
let tmpCombination = bestSum(tmp, numbers, memo);
if (tmpCombination !== null) {
shortestRes =
shortestRes === null ||
shortestRes.length > tmpCombination.length + 1
? [num, ...tmpCombination]
: shortestRes;
}
}
memo[key] = shortestRes;
return memo[key];
};
res = bestSum(8, [2, 3, 5], {});
res;
|
DP table
State machine
State transaction equation
DP problem Example
I have another post to classify dp problem
See this Post