Avatar

dynamic programming

Van Truong

algorithm

Let get started with the *Fibonacci sequence problem*, `F[n] = F[n-1] + F[n-2]`

- __*Bottom up*__

```js
const f = new Array(N+1);
f[0] = 0;
f[1] = 1;

for (let i = 2; i <= N; i++) {
  f[i] = f[i-1] + f[i-2];
}

return f[n]
```

- __*Top down*__ use `recursion` + `memoization` (cache)

```js
const f = new Array(N+1).fill(-1); // use -1 to mark as not calculated

function cal(int i) {
  if (i == 0) return 0;
  if (i == 1) return 1;

  if(f[i] != -1) return f[i];
  f[i] = cal(i-1) + cal(i-2);
  return f[i];
}

return cal(n);
```

### When to use DP ?

- Counting problems: count number of way to do something.
  - [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)

- Optimisation problems:
  - find min (`BFS` => `dijkstra` => `DP`)
  - find max
  - pattern: deciding to do something at one step may affect the ability to do something in the future.

__Example 1:__ [Longest Increasing Subsequence (LIS)](https://leetcode.com/problems/longest-increasing-subsequence/)

__Step 1__: Defining state:
- `f[i]` length of the longest increasing subsequence that __ended at__ `A[i]`

__Step 2__: Find the relation between problems and it subproblems
- `f[i] = max(f[j] + 1)` with the conditions `A[j] < A[i]` and `j < i`

__Step 3__: Base cases: `f[0] = 1`

```js
// Bottom up approach
var lengthOfLIS = function(nums) {
    const size = nums.length;
    const f = new Array(size).fill(1); // f[i] LIS that ended with nums[i]
    f[0] = 1;

    for(let i = 1; i < size; i++) {
        for(j = 0; j < i; j++) {
            if(nums[i] > nums[j]) {
                f[i] = Math.max(f[i], f[j] + 1);
            }
        }
    }

    let res = f[0];
    for(let i = 1; i < size; i++) {
        res = Math.max(res, f[i]);
    }

    return res;
};
```

```cpp
// Top-down approach

vector<int> fx(n, -1);
int lengthOfLIS(int i) { // to calculate f[i]
	if (fx[i] != -1) return fx[i]; // cache
	if (i == 0) return fx[i] = 1; // base
	int res = 1;
	for(int j = i-1; j >= 0; j–-) { // O(N)
		if (a[i] > a[j]) {
			res = max(res, lengthOfLIS(j) + 1);
		}
}
fx[i] = res;
return res;
}
```

__*Other examples*__:
- [House Robber](https://leetcode.com/problems/house-robber/)
- [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)

__Example 2:__ [Longest Common Subsequence (LCS)](https://leetcode.com/problems/longest-common-subsequence/)

__Step 1__: Defining state:
- `f[i][j]`: the len of longest common sequence when considering `s[0…i]` and `t[0..j]`

__Step 2__: Find the relation between problems and it subproblems

```py
if s[i] == t[j]:
	f[i][j] = f[i-1][j-1] + 1

if s[i] != t[j]:
	f[i][j] = max(f[i-1][j], f[i][j-1])
```

```js
// Solution for https://leetcode.com/problems/longest-common-subsequence/

var longestCommonSubsequence = function (text1, text2) {
  const N1 = text1.length;
  const N2 = text2.length;

  const fx = new Array(N1 + 1); // fx[i][j]: LCS text1[0..i-1] & text2[0..j-1]
  for (let i = 0; i < N1 + 1; i++) {
    fx[i] = new Array(N2 + 1).fill(0);
  }

  for (let i = 1; i < N1 + 1; i++) {
    for (let j = 1; j < N2 + 1; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        fx[i][j] = fx[i - 1][j - 1] + 1;
      } else {
        fx[i][j] = Math.max(fx[i - 1][j], fx[i][j - 1]);
      }
    }
  }

  return fx[N1][N2];
};
```


Understand dynamic programming step by step

TAGGED POSTS algorithm

Dynamic Programming