# 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://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).
```
Sign in with Wallet
Connect another wallet