---
# System prepended metadata

title: Dynamic Programming

---

# Dynamic Programming
> account: lyp
> password: Apcs510562

### APCSC #dp04
https://judge.apcs.camp/problems/31

```
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + value[i][j]
```

### APCSC #dp05
https://judge.apcs.camp/problems/32

```
dp[i][j] = 從(0,0)走到(i,j)的方法數
if (isObstacle(i,j)) {
    dp[i][j] = 0;
}
else {
    // the range of integer: - 2^31 ~ 2^31 - 1, -2*10^9 ~ 2*10^9 
    dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
}

```

| Column 1 | Column 2 | Column 3 |
| -------- | -------- | -------- |
|   1   |  1    |  1    |
|   1   |  2    |  3    |
|   1   |  3    |  6    |

#### 式子裡有減號(1)
```
dp[i][j] = (dp[i-1][j] - dp[i][j-1] + 1000000007) % 1000000007;

-2 % 5 = 3
(-2 + 5) % 5 = 3
```

#### 式子裡有減號(2)
```
dp[i][j] = ((dp[i-1][j] - 100*dp[i][j-1]) % 1000000007 + 1000000007) % 1000000007

-2000 % 7 = -5
(-5 + 7) % 7 = 2
```



### APCSC #dp42
https://judge.apcs.camp/problems/66

```
0 -> green
1 -> blue
2 -> red
dp[i][0] = 前i個數字都已經塗色，且第i個為綠色，的最大值
dp[i][1] = 前i個數字都已經塗色，且第i個為藍色，的最大值
dp[i][2] = 前i個數字都已經塗色，且第i個為紅色，的最大值

dp[i+1][0] = max(dp[i][1], dp[i][2]) + value[i+1];
dp[i+1][1] = max(dp[i][0], dp[i][2]);
dp[i+1][2] = max(dp[i][0], dp[i][1]) - value[i+1];

answer = max(dp[N-1][0], dp[N-1][1], dp[N-1][2]);
```

### APCSC #dp34
https://judge.apcs.camp/problems/60
```
dp[i][0] = 第i個字母以前，出現幾個單獨的q
dp[i][1] = 第i個字母以前，出現幾個qw
dp[i][2] = 第i個字母以前，出現幾個qwq

if (str[i] == 'q') {
    dp[i][0] = dp[i-1][0] + 1;
    dp[i][1] = dp[i-1][1];
    dp[i][2] = dp[i-1][2] + dp[i-1][1];
} else if(str[i] == 'w') {
    dp[i][0] = dp[i-1][0];
    dp[i][1] = dp[i-1][1] + dp[i-1][0];
    dp[i][2] = dp[i-2][2];
} else {
    dp[i][0] = dp[i-1][0];
    dp[i][1] = dp[i-1][1];
    dp[i][2] = dp[i-1][2];
}

// here
dp[i][0] = 第i個字母以前，出現幾個單獨的q
dp[i][1] = 第i個字母以前，出現幾個qw
dp[i][2] = 第i個字母以前，出現幾個qwq

if (str[i] == 'q') {
    dp[i][0] = dp[i-1][0]+1;
} else {
    dp[i][0] = dp[i-1][0];
}

if (str[i] == 'w') {
    dp[i][1] = dp[i-1][1]+dp[i-1][0];
} else {
    dp[i][1] = dp[i-1][1];
}

if (str[i] == 'r') {
    dp[i][2] = dp[i-1][2]+dp[i-1][1];
} else {
    dp[i][2] = dp[i-1][2];
}
answer = dp[N-1][2]
```
### APCSC #dp13 區間dp
N個沙堡，每次合併可以合併相鄰兩個，合併後順序不變，但合併的時候要付出x+y塊錢，x和y是被合併的兩個沙堡的重量。你的最終目標是要把所有的沙堡合併成為一個大沙堡，請問最少要花多少錢？
```
exampe:
[1, 2, 3, 4] -> [3, 3, 4] -> [6, 4] -> [10]
3 + 6 + 10

[......] -> [...] + [...] -> final

[a_1, a_2, ..., a_n] -> [a_1, ..., a_i] + [a_(i+1), ...a_n]

dp[L][R]: 把第L個到第R個沙堡全部合併起來的成本。
dp[1][N]: 答案在這裡

dp[L][R] = min(dp[L][M] + dp[M+1][R] + sum(input[L~R]))
         = min(dp[L][M] + dp[M+1][R]) + sum(input[L~R])
         , for all M in [L, R-1]

// initialize others with INF
for (int i = 0; i <= N; i++)
    dp[i][i] = 0;

for (int i = 0 ; i < N ; i++){
    int cnt = 0;
    while(cnt < N-1-i){
        cnt++;
        int L = cnt, R = i + cnt + 1;
        for(int M = cnt ; M <= i+cnt+1 ; M++){
            dp[L][R] = min(dp[L][R], dp[L][M] + dp[M+1][R]) + sum(input[L:R]);
        }
    }
}


// a clearer version
for (int length = 1; length <= N-1; length++) {
    for (int L = 1; L <= N - length; L ++) {
        // calculate dp[L][L+length]
        int R = L + length;
        for (int M = L; M < R; M++) {
            dp[L][R] = min(dp[L][R], dp[L][M] + dp[M+1][R] + sum(input[L~R]));
        }
    }
}


```
![](https://i.imgur.com/okNMrRn.png)

https://judge.apcs.camp/problems/40
### APCSC #dp15
https://judge.apcs.camp/problems/42


### Longest Common Subsequence
```
example:
s_1 = "aabbcc", s_2 = "aabbbc"
LCS = "aabbc"
```

### Edit distance
```
s_1 = "aabbcc", s_2 = "aabbbc"
* insert
* replace
* remove

dp[i][j]: s_1[1~i] 要變成 s_2[1~j]

if (s1[i] == s2[j]) {
    dp[i][j] = dp[i-1][j-1];
} else {
    (1) replace
    dp[i][j] = dp[i-1][j-1] + 1;
    (2) insert
    dp[i][j] = dp[i][j-1] + 1;
    
    (3) remove
    dp[i][j] = dp[i-1][j] + 1;
}

```

### 矩陣乘法問題
```
A: (x, y)
B: (y, z)
A*B: (x, z)

兩個矩陣相乘，需要幾個步驟。
A*B所需要的乘法次數：x*y*z。

A*B*C*D*E = (A*B)*(C)*(D*E)

A*B*C = (A*B)*C = A*(B*C)

A: (w, x), B: (x, y), C: (y, z)
w*x*y + w*y*z v.s. x*y*z + w*x*z
(w*y)*(x+z) v.s. (x*z)*(x+w)

A*B*C*D*E = A*(B*C*D*E) = (A*B)*(C*D*E) = ... = ...

dp[1][n] = max(dp[1][1]+dp[2][n]+cost(), dp[1][2]+dp[3][n], ...)

dp[l][r] = max(dp[l][k] + dp[k+1][r] + height(l)*width(k)*width(r));
= max(dp[l][k] + dp[k+1][r] + height(l)*height(k+1)*width(r));
```

照片: (1920, 1080) -> (1, 1920*1080)

input: (1, 3)
1-st hidden layer: (1, 3) * (3, 4) = (1, 4)

input: (1, 1920*1080)
1-st hidden layer: (1, 1920*1080) * (1920*1080, 20000) = (1, 20000)

### 2D區間和
```
1-D prefix sum:
[1, 2, 3, 4, 5] -> [1, 3, 5, 10, 15]

2-D prefix sum:
[1, 2, 3, 4]
[9, 5, 6, 2]
[5, 5, 5, 5]


[ 1,  3,  6, 10]
[10, 17, 26, 32]
[.......]

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j]
(左上角是(1,1)、右下角是(i,j)的matrix總和)

那怎麼算左上角是(x1, y1)、右下角是(x2, y2)的matrix總和？
dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

用O(N*M)的時間預處理，然後每次查詢子矩陣的總和都是O(1)。
```

### 面積最大方陣
```
[0, 1, 1, 1]
[1, 1, 1, 0]
[0, 1, 1, 0]
[1, 1, 1, 0]

Answer: 2*2 = 4

dp[i][j]: 以(i,j)為右下角的最大方陣的邊長
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 (if a[i][j] == 1)

Where is our answer?
max(dp[i][j]), for all i, j
```

### Blocks
https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1500
```
任何一個sequence，最後消掉的顏色一定可以是最左邊或最右邊的顏色，反正是左邊是右邊都沒差，那我們就假設是右邊。

input: [0, 1, 1, 1, 1, 2, 2, 2, 0] -> [(0, 1), (1, 4), (2, 3), (0, 1)]

答案在這格：
dp[1][4] = max(dp[1][3] + 1^2, dp[2][3] + 2^2)

input: [0, 1, 0, 1, 0]
dp[1][5] = max(dp[2][4] + 2^2)


Next week we will introduce:
dp[L][R][t]

```

### Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/

### Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

```
i: i-th day
k: k-th transaction
dp[k][i] = the maximum profit after finishing the k-th transaction before the i-th day
dp[k][i] = max(dp[k][i-1], dp[k-1][i-t] + price[i] - price[i-t]);

If we enumerate all the possible t, the time complexity is O(K*N*N).

In this case, K = 2. So O(N*N);

Let j = i-t, 0 <= j < i.
dp[k][i] = max(dp[k][i-1], max(dp[k-1][j] + price[i] - price[j]) );

Look closer at max(dp[k-1][j] + price[i] - price[j])
= max(dp[k-1][j] - price[j]) + price[i]

Let profitMinusPrice[k][j] = dp[k][j] - price[j].

max(dp[k-1][j] + price[i] - price[j])
= max(dp[k-1][j] - price[j]) + price[i]
= max(profitMinusPrice[k-1][j]) + price[i]
-> O(1)

To calculate dp[k][i], O(1).
The time complexity of the whole task is O(k*N).
```