# 演算法課程題解 - 動態規劃\: 基本不定型
# Kattis Riječi
## 題目
https://open.kattis.com/problems/rijeci
有一台機器可以顯示字串，當按下按鈕之後會開始顯示字串，並且每次觸發會轉換成新的字串，規律如下
`A` -> `B` -> `BA` -> `BAB` -> `BABBA` -> `BABBABAB` -> ...
也就是每次會將上一個字串接上前一個字串就會升成新的字串
現在告訴你按鈕被觸發了幾次，請問 `A` 以及 `B` 分別共出現了幾次
## 想法 By Koios
因為每次都是將前兩個字串合併行成新的字串
所以 `A` 以及 `B` 出現的次數也會等同前兩個字串數量相加
會影響到答案的只有按鈕觸發的次數，這就是 DP 的狀態
至於轉移，根據上面的推論可以得到 $A_i = A_{i-1} + A_{i-2} \quad B_i = B_{i-1} + B_{i-2}$
初始狀態 $A_0 = 1, A_1 = 0 \quad B_0 = 0, B_1 = 1$
有了狀態、轉移、初始狀態，我們就完成 DP 的要件了
接下來你可以選擇要用 Buttom-up 或是 Top-down，以下示範兩種方式
如果你選擇的是 Top-down，記得上課提到費氏數列的例子，要避免同樣問題重複詢問，需要用陣列紀錄結果
### 程式碼 - Buttom-up
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, A[50], B[50];
int main(){
A[0] = 1, A[1] = 0;
B[0] = 0, B[1] = 1;
for(int i=2 ; i<50 ; i++){
A[i] = A[i-1] + A[i-2];
B[i] = B[i-1] + B[i-2];
}
cin>>n;
cout<<A[n]<<" "<<B[n]<<"\n";
return 0;
}
```
### 時間複雜度分析
令 $N = 50$
總時間複雜度為 $O(N)$
### 程式碼 - Top-down
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, dp_A[50], dp_B[50];
int A(int depth){
if(depth == 0) return 1;
if(depth == 1) return 0;
if(dp_A[depth-1] == 0) dp_A[depth-1] = A(depth-1);
if(dp_A[depth-2] == 0) dp_A[depth-2] = A(depth-2);
return dp_A[depth-1] + dp_A[depth-2];
}
int B(int depth){
if(depth == 0) return 0;
if(depth == 1) return 1;
if(dp_B[depth-1] == 0) dp_B[depth-1] = B(depth-1);
if(dp_B[depth-2] == 0) dp_B[depth-2] = B(depth-2);
return dp_B[depth-1] + dp_B[depth-2];
}
int main(){
cin>>n;
cout<<A(n)<<" "<<B(n)<<"\n";
return 0;
}
```
### 時間複雜度分析
在沒有 DP 的情況下，複雜度最差為 $O(2^n)$
不過現在有了 DP，每個 DP 值最多被更新一次，更新後的詢問時間複雜度降至 $O(1)$
總時間複雜度為 $O(n)$
# UVa 369
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?369
給定 $N, M$ ，求排列組合中的組合數 $C^{N}_{M}$
$5 \leq N, M \leq 100 \\ M \leq N$
$C = \frac{N!}{(N-M)! \times M!}$
## 想法 By Koios
組合的定義是從 $N$ 個物品中取 $M$ 個任意排列，移除掉取的物品相同但排列方式不同的情況
組合有以下的性質
1. $C^{N}_{1} = N$
2. $C^{N}_{N} = 1$
3. $C^{N}_{M} = 0 \ (N < M)$
4. $C^{N}_{M} = C^{N-1}_{M} + C^{N-1}_{M-1}$
:::info
關於這個性質可以這樣思考
從 $N$ 個物品取出 $M$ 個組合，那麼最後一個元素可以選擇選或不選
如果最後一個元素要選，那麼剩下的 $N-1$ 個元素還需要選出 $M-1$ 個
如果最後一個元素不選，那麼剩下的 $N-1$ 個元素還需要選出 $M$ 個
:::
會影響組合數的就是 $N, M$，這也就是 DP 的狀態
藉由第四個性質可以得到轉移式
藉由前三個性質可以得到初始狀態
有了狀態、轉移、初始狀態，我們就完成 DP 的要件了
接下來你可以選擇要用 Buttom-up 或是 Top-down，以下示範兩種方式
### 程式碼 - Buttom-up
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
long long C[105][105];
int n, m;
int main(){
for(int i=0 ; i<=100 ; i++){
for(int j=1 ; j<=100 ; j++){
if(j==1) C[i][j] = i;
else if(i==j) C[i][j] = 1;
else if(i<j) C[i][j] = 0;
else C[i][j] = C[i-1][j] + C[i-1][j-1];
}
}
while(cin>>n>>m && (n!=0 || m!=0)){
cout<<n<<" things taken "<<m<<" at a time is "<<C[n][m]<<" exactly.\n";
}
return 0;
}
```
### 時間複雜度分析
令 $N = 100$
預處理時間複雜度為 $O(N^2)$
詢問時間複雜度為 $O(1)$，假設總共詢問 $Q$ 次
總時間複雜度為 $O(N^2 + Q)$
### 程式碼 - Top-down
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
long long C[105][105];
int n, m;
int Combine(int i, int j){
if(C[i][j]) return C[i][j];
if(j == 1) return i;
if(i == j) return 1;
if(i<j) return 0;
C[i-1][j] = Combine(i-1, j);
C[i-1][j-1] = Combine(i-1, j-1);
return C[i-1][j] + C[i-1][j-1];
}
int main(){
while(cin>>n>>m && (n!=0 || m!=0)){
cout<<n<<" things taken "<<m<<" at a time is "<<Combine(n, m)<<" exactly.\n";
}
return 0;
}
```
# TOJ 470
## 題目
https://toj.tfcis.org/oj/pro/470/
你憑藉著極大的熱情與努力，獲得了學科能力競賽的選手資格
現在你想要利用盡量多的公假來練習，但是你的老師並不同意
儘管你不願意，你還是決定要敷衍一下，請公假時讓使魔擬態
不過老師畢竟是老師，只要連續兩天都讓使魔擬態就會被發現
現在告訴你每天訓練分別會有多少訓練成效，求最大成效總和
## 想法 By Koios
每天都可以選擇是否要請公假訓練
那麼如果今天選擇不訓練，最大成效就會是前一天訓練成效最大值
反之如果今天選擇要訓練，最大成效就會是前一天不訓練的訓練成效最大值，加上今日訓練的成效值
定義 $dp[i][j]$ 表示第 $i$ 天選擇是否要訓練 $(j = 1 \texttt{ or } 0)$ 的最大訓練成效
那麼我們可以得出這樣的轉移式
$$
\begin{cases}
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) \\
dp[i][1] = max(dp[i-1][0], dp[i][1]) + arr[i]
\end{cases}
$$
並且
$$
dp[0][0] = 0 \\
dp[0][1] = arr[0]
$$
如此一來就完成 DP 的要素了
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, arr[1000010], dp[1000010][2];
int main(){
while(cin>>n){
for(int i=0 ; i<n ; i++){
cin>>arr[i];
dp[i][0] = dp[i][1] = 0;
}
dp[0][0] = 0;
dp[0][1] = arr[0];
for(int i=1 ; i<n ; i++){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = max(dp[i][1], dp[i-1][0] + arr[i]);
}
cout<<max(dp[n-1][0], dp[n-1][1])<<"\n";
}
return 0;
}
```
## 優化
從上面的 DP 轉移式當中會發現到，實際上我們需要的資訊只有前一個 DP 值，所以我們並不需要前一個以前的 DP 值
那麼 $dp[i][j]$ 的 $i$ 值就只需要 $0, 1$ 即可
如果當前取的 $i$ 值是 $0$，那麼前一個 DP 值就會存在 $i$ 值為 $1$ 的位置
反之，如果當前取的 $i$ 值是 $1$，那麼前一個 DP 值就會存在 $i$ 值為 $0$ 的位置
現在 DP 式改為
$$
\begin{cases}
dp[i\%2][0] = max(dp[(i-1)\%2][0], dp[(i-1)\%2][1]) \\
dp[i\%2][1] = max(dp[(i-1)\%2][0], dp[i\%2][1]) + arr[i]
\end{cases}
$$
最後答案為 $max(dp[(n-1)\%2][0], dp[(n-1)\%2][1])$
最後的最後，我們還可以把 dp 的計算都整理進輸入的迴圈內
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, tmp, dp[2][2];
int main(){
while(cin>>n){
dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
cin>>dp[0][1];
for(int i=1 ; i<n ; i++){
cin>>tmp;
dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-1)%2][1]);
dp[i%2][1] = max(dp[i%2][1], dp[(i-1)%2][0] + tmp);
}
cout<<max(dp[(n-1)%2][0], dp[(n-1)%2][1])<<"\n";
}
return 0;
}
```
### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資建表時間複雜度為 $O(n)$
每筆測資總時間複雜度為 $O(n)$
# TOJ 540
## 題目
https://toj.tfcis.org/oj/pro/540/
在一場鐵人三項的比賽當中，每個選手都必須依序進行**游泳**、**腳踏車**、**跑步**，不過不限制各路段的使用方式，也就是說你可以在柏油路上游泳、在水上跑步
我們已經是先探勘好場地，知道在每個路段上使用三種運動各需要消耗多少時間，問最短消耗時間為何
## 想法 By Koios
在每個路段上選擇使用某運動，則上一段只可能是上一種活動或是同一種活動
舉例來說，這個路段要選擇**騎腳踏車**，那麼上一段只可能是**游泳**或是**腳踏車**
定義 $dp[i][j]$ 表示在第 $i$ 個路段上使用 $j$ 運動所消耗的最短時間
定義 $arr[j][i]$ 表示在第 $i$ 個路段上使用 $j$ 運動所消耗的時間
其中 $j$ 依序表示**游泳**、**腳踏車**、**跑步**
可以得到轉移式
$$
\begin{cases}
dp[i][0] = dp[i-1][0] + arr[0][i] \\
dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + arr[1][i] \quad (i \geq 1)\\
dp[i][2] = min(dp[i-1][2], dp[i-1][1]) + arr[2][i] \quad (i \geq 2)
\end{cases}
$$
並且
$$
dp[0][0] = arr[0][0] \\
dp[0][1] = dp[0][2] = dp[1][2] = \infty
$$
可以直接令 $10^9$ 是無限大
而最後答案為 $dp[n-1][2]$
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, arr[4][200005];
long long dp[200005][4];
int main(){
cin>>n;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<3 ; j++){
cin>>arr[j][i];
}
}
dp[0][0] = arr[0][0];
dp[0][1] = dp[0][2] = dp[1][2] = 1e9+10;
for(int i=1 ; i<n ; i++){
dp[i][0] = dp[i-1][0] + arr[0][i];
if(i >= 1)
dp[i][1] = min(dp[i-1][1], dp[i-1][0]) + arr[1][i];
if(i >= 2)
dp[i][2] = min(dp[i-1][2], dp[i-1][1]) + arr[2][i];
}
cout<<dp[n-1][2]<<"\n";
return 0;
}
```
## 優化
從上面的程式碼中可以發現到
1. 輸入的 $arr[j][i]$ 實際上各只會用到一次
2. $dp$ 的每一項只跟上一項有關係
由第一點可以發現 $dp$ 的計算可以直接在輸入階段跟著做，而且不需要 $arr$ 陣列了，只需要一個變數即可
由第二點可以發現 $dp$ 不需要那麼大的空間，所以可以用取餘數的技巧來簡化空間使用
另外，在計算每個運動項目的 $dp$ 值，前提條件都是 $i$ 必須至少 $\geq j$ ，所以可以再化簡一點程式碼
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, m;
long long dp[2][4];
int main(){
cin>>n;
// 為了避免減1後出現負數，從 1 開始
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=3 ; j++){
dp[i%2+1][j] = 1e9+10;
cin>>m;
if(j == 1)
dp[i%2+1][j] = dp[(i-1)%2+1][j] + m;
else if(i >= j)
dp[i%2+1][j] = min(dp[(i-1)%2+1][j-1], dp[(i-1)%2+1][j]) + m;
}
}
cout<<dp[n%2+1][3]<<"\n";
return 0;
}
```
### 時間複雜度分析
輸入以及 DP 時間複雜度皆為 $O(n)$
總時間複雜度為 $O(n)$
# TOJ 508
## 題目
https://toj.tfcis.org/oj/pro/508/
定義一條完美河道是由高度 $9$ 每次移動一格只遞減 $1$，並且最終高度為 $0$
現在給你 $N \times M$ 的長方形區域，只由 $0$~$9$ 的數字組成請問其中有多少條完美河道
## 想法 By Koios
跟爬樓梯的問題很類似，假如看做是從 $0$ 爬到 $9$，那麼每個高度 $h$ 都是從高度 $h-1$ 轉移過來
為了避免重複詢問相同的問題，我們可以利用 dp 的方式把已知的答案儲存起來，下次詢問的時候就直接回答
定義 $dp[i][j]$ 表示有多少條從 $0$ 開始每次遞增 $1$ 到 $(i, j)$ 這格的河道
定義 $arr[i][j]$ 表示在 $(i, j)$ 的數字
則有轉移式
$$
\begin{cases}
dp[i][j] = dp[i-1][j] + 1 \quad \texttt{if arr[i][j] = arr[i-1][j] + 1} \\
dp[i][j] = dp[i][j-1] + 1 \quad \texttt{if arr[i][j] = arr[i][j-1] + 1} \\
dp[i][j] = dp[i+1][j] + 1 \quad \texttt{if arr[i][j] = arr[i+1][j] + 1} \\
dp[i][j] = dp[i][j+1] + 1 \quad \texttt{if arr[i][j] = arr[i][j+1] + 1}
\end{cases}
$$
並且
$$
dp[i][j] = 1 \quad \texttt{if arr[i][j] = 0}
$$
這裡使用 Top-down 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n, m, ans, dp[1005][1005];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
char arr[1005][1005];
int dfs(int x, int y){
if(arr[x][y] == '0') return dp[x][y] = 1;
// 記得有找過答案就直接回傳
if(dp[x][y]) return dp[x][y];
int res = 0;
for(int i=0 ; i<4 ; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >=m || arr[nx][ny] + 1 != arr[x][y]) continue;
res += dfs(nx, ny);
}
return dp[x][y] = res;
}
int main(){
cin>>n>>m;
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
cin>>arr[i][j];
}
}
for(int i=0 ; i<n ; i++){
for(int j=0 ; j<m ; j++){
if(arr[i][j] == '9')
ans += dfs(i, j);
}
}
cout<<ans<<'\n';
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(NM)$
DFS 每個格子最多被拜訪一次，時間複雜度為 $O(NM)$
總時間複雜度為 $O(NM)$
# UVa 10198
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10198
有個人知道怎麼做算數，現在正在學習寫數字
他已經學會怎麼寫 $1, 2, 3, 4$ 了，不過他還沒發現到 $1$ 和 $4$ 的差別，所以他認為 $4$ 是 $1$ 的另一種寫法
現在他正在玩數字求和的遊戲，他會把幾個 $1$~$4$ 的數字相加，組成新的數字(新的數字可以包含 $1$~$4$ 以外的數字)
現在給你一個正整數 $N$，請問在只用 $1$~$4$ 這四個數字的情況下，你可以有多少種寫來表示數字 $N$?
例如 $2$ 可以用 $1+1$, $1+4$, $4+1$, $4+4$, $2$ 這五種寫法
## 想法 By Koios
$N$ 可以用很多 $1$~$4$ 相加而成
要問 $N$ 有多少種表示方式，可以看看最後一個選取的數字是 $1$~$4$ 的哪一個
選取完最後一個數字，就得到了子問題
例如最後一個數字選擇 $1$，那麼子問題就是 $N-1$ 有多少的組成方式
定義 $dp[i]$ 表示數字 $i$ 有多少表示方式
則有轉移式
$$
dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-1]
$$
並且
$$
\begin{cases}
dp[i] = 0 \quad \texttt{if i <= 0} \\
dp[1] = 2 \\
dp[2] = 5 \\
dp[3] = 13
\end{cases}
$$
這裡使用 Top-down 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n;
long long dp[1005];
long long sol(int n){
if(n <= 0) return 0;
if(dp[n]) return dp[n];
return dp[n] = sol(n-1)*2 + sol(n-2) + sol(n-3);
}
int main(){
dp[1] = 2; dp[2] = 5; dp[3] = 13;
while(cin>>n){
cout<<sol(n)<<"\n";
}
return 0;
}
```
概念上是對了，但是因為這題的數字會很大，大到超過 long long 的大小，所以需要大數運算
這裡只是希望大家練習 DP 的想法，所以不詳細說明如何進行大數運算，這裡推薦一個模板讓大家使用
http://sunmoon-template.blogspot.com/2015/01/big-interger.html
直接把程式碼貼上去，把 dp 陣列的 long long 改成 bigN 型態即可
# UVa 11067
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11067
大家應該都看過小紅帽的故事，如果當初他知道大野狼所在的位置，接下來就不會有那麼多麻煩事出現
今天有一個 $W \times H$ 的網狀方格地圖，地圖上有 $(W+1) \times (H+1)$ 個點
小紅帽的家位於地圖左下角 $(0, 0)$ 的位置，而奶奶家位在地圖右上角 $(W, H)$ 的位置
小紅帽要從家裡前往奶奶家，並且希望用最少步數(也就是只能向右或是向上走一步)
告訴你大野狼在森林中可能出現的位置有哪些，請問在使用最少步數且避開大野狼可能出現的地點的前提下，小紅帽有幾種到達奶奶家的方式
## 想法 By Koios
這題地圖的 $(0, 0)$ 雖然是在左下角，但是其實上下顛倒也對答案沒有影響，在陣列使用上也比較直觀
所以不妨想成小紅帽在左上角，奶奶在右下角，每次只能向右或是向下走
對於每個點，只能從左邊以及上面轉移過來
定義 $dp[i][j]$ 表示 $(i, j)$ 的移動方式
則有轉移式
$$
dp[i][j] = dp[i-1][j] + dp[i][j-1]
$$
並且
$$
\begin{cases}
dp[0][0] = 1 \\
dp[i][j] = 0 \quad \texttt{if (i, j) has wolf}
\end{cases}
$$
這裡用 Top-down 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int w, h, n;
long long dp[105][105];
long long sol(int x, int y){
if(dp[x][y] > 0) return dp[x][y];
if(dp[x][y] < 0) return 0;
long long res=0;
// left
if(y-1 >= 0) res += sol(x, y-1);
// down
if(x-1 >= 0) res += sol(x-1, y);
return dp[x][y] = res;
}
int main(){
while(cin>>w>>h && (w!=0 || h!=0)){
// 注意格子點數是 (W+1)*(H+1)
for(int i=0 ; i<w+1 ; i++){
for(int j=0 ; j<h+1 ; j++){
dp[i][j] = 0;
}
}
dp[0][0] = 1;
cin>>n;
for(int i=0, x, y ; i<n ; i++){
cin>>x>>y;
dp[x][y] = -1;
}
long long ans = sol(w, h);
if(ans == 0)
cout<<"There is no path.\n";
else if(ans == 1)
cout<<"There is one path from Little Red Riding Hood's house to her grandmother's house.\n";
else
cout<<"There are "<<ans<<" paths from Little Red Riding Hood's house to her grandmother's house.\n";
}
return 0;
}
```
# UVa 10081
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10081
定義一個數字是**緊密的**，唯有每個相鄰的數字之間不會差距超過 $1$
現在給定正整數 $k, n$， $0 \leq k \leq 9$ ，請問在使用 $0$~$k$ 這幾個數字組出長度為 $n$ 的數字中，有多少比例的數字是緊密的
## 想法 By Koios
要計算比例就需要知道總共能組出多少數字，總共有多少組是緊密的數字
全部的組數可以用排列組合的觀念來想，每個位數都有 $0$~$k$ 這 $k+1$ 種數字，總共有 $(k+1)^{n}$ 種
至於計算緊密數字，可以想成最後一個數字要放多少，如此一來就可以找到子問題
例如最後選擇放 $m$，那麼上個數字只能是 $m-1, m, m+1$ 這三種，長度 $n-1$ 的子問題就出現了
定義 $dp[i][j]$ 表示第 $i$ 個數字放 $j$ 的方法數
則有轉移式
$$
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]
$$
並且
$$
dp[0][i] = 1 \quad 0 \leq i \leq k
$$
這裡使用 Buttom-up 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int k, n;
long long dp[105][10];
int main(){
while(cin>>k>>n){
for(int i=0 ; i<105 ; i++){
for(int j=0 ; j<10 ; j++){
if(i == 0)
dp[i][j] = 1;
else
dp[i][j] = 0;
}
}
for(int i=1 ; i<n ; i++){
for(int j=0 ; j<=k ; j++){
if(j-1 >= 0)
dp[i][j] = dp[i][j] + dp[i-1][j-1];
dp[i][j] = dp[i][j] + dp[i-1][j];
if(j+1 <= k)
dp[i][j] = dp[i][j] + dp[i-1][j+1];
}
}
long long cnt = 0, tot=pow(k+1, n);
for(int i=0 ; i<=k ; i++){
cnt = cnt + dp[n-1][i];
}
cout<<fixed<<setprecision(5)<<100*((double)(cnt)/(double)(tot))<<"\n";
}
return 0;
}
```
概念上是對了，但是因為這題的數字會很大，大到超過 long long 的大小，所以需要大數運算
這裡只是希望大家練習 DP 的想法，所以不詳細說明如何進行大數運算，這裡推薦一個模板讓大家使用
http://sunmoon-template.blogspot.com/2015/01/big-interger.html
直接把程式碼貼上去，把 long long 改成 bigN 型態並且自己實作快速冪(qpow) 即可
# UVa 10450
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10450
在一場比賽當中，粉絲會使用氣笛來加油，不過氣笛只要連續吹 $2$ 秒就會壞掉
現在給你一個正整數 $n$ ，請問在長度 $n$ 的0/1字串當中，可以有多少安排方式使得不會出現任何兩個 $1$ 相鄰的情況
## 想法 By Koios
我們可以看第 $n$ 個字要放 $0$ 或是 $1$，這樣就得到了子問題: 第 $n-1$ 個字要放什麼
定義 $dp[i][j]$ 表示第 $i$ 格選擇放 $j$ 的方法數
則有轉移式
$$
\begin{cases}
dp[i][0] = dp[i-1][0] + dp[i-1][1] \\
dp[i][1] = dp[i-1][0]
\end{cases}
$$
並且
$$
\begin{cases}
dp[0][0] = 1 \\
dp[0][1] = 1
\end{cases}
$$
同樣的，因為發現到 $dp$ 實際上只跟前一項有關，所以可以利用取餘數優化記憶體使用量
這裡以 Buttom-up 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int t, n;
long long dp[2][2];
int main(){
cin>>t;
for(int Case=1 ; Case<=t ; Case++){
cin>>n;
dp[0][0] = dp[0][1] = 1;
for(int i=1 ; i<n ; i++){
dp[i%2][0] = dp[(i-1)%2][0] + dp[(i-1)%2][1];
dp[i%2][1] = dp[(i-1)%2][0];
}
cout<<"Scenario #"<<Case<<":\n"<<dp[(n-1)%2][0]+dp[(n-1)%2][1]<<"\n\n";
}
return 0;
}
```
# UVa 10036
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10036
給一個長度 $n$ 的序列，你要在兩兩數字之間插入 `+` 或 `-`
請問是否有機會使得計算結果模一個正整數 $k$ 為 $0$
## 想法
因為問的是能不能整除，所以我們**只需要考慮餘數**即可
如果在第 $i$ 個數字可以餘 $m$，那麼第 $i+1$ 個數字就可以餘 $(m+arr[i+1])%k$ 以及 $(m-arr[i+1])%k$
定義 $dp[i][j]$ 表示前 $i$ 個數字是否可以餘 $j$
為了將餘數為負數也考慮進來，一律將餘數加上 $100$
則有轉移式
$$
dp[i][j] = dp[i-1][(m - arr[i] + 100)] \texttt{ || } dp[i-1][(m + arr[i] + 100)] \quad -k \leq m \leq k
$$
並且
$$
dp[0][(arr[0]+100)\%k] = 1
$$
這裡以 Buttom-up 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int t, n, k, m;
bool dp[10005][205];
int main(){
cin>>t;
while(t--){
for(int i=0 ; i<10005 ; i++){
for(int j=0 ; j<205 ; j++){
dp[i][j] = false;
}
}
cin>>n>>k;
for(int i=0 ; i<n ; i++){
cin>>m;
m%=k;
if(i == 0) dp[i][m+100] = true;
else{
for(int j=0 ; j<=k+100 ; j++){
if(dp[i-1][j]){
dp[i][(j-100+m)%k+100] = true;
dp[i][(j-100-m)%k+100] = true;
}
}
}
}
if(dp[n-1][100]) cout<<"Divisible\n";
else cout<<"Not divisible\n";
}
return 0;
}
```
# UVa 116
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?116
有一個 $m \times n$ 的方格，每個格子當中都有一個數字表示權重，本題希望找到總權重最小的路徑
每條路徑必定都是從第一行開始，每次從第 $i$ 行走到第 $i+1$ 行
走下一步的方式有三種，如下圖
<center><img src="https://i.imgur.com/IEydiKx.png"></center>
並且第一列以及最後一列可以看做是相鄰的，也就是說可以看做是圓柱的樣子，上下是包起來的
一個路徑的總權重指的是路徑上權重的總和
請找出 $m \times n$ 的方格當中，總權重最小的路徑以及最小的總權重
如果存在相同權重解法，請輸出字典序最小的
路徑請依序輸出各直行選擇了第幾列
## 想法 By Koios
每個方格都有三種移動方式，可以用 DFS 將三個格子都走過一遍，去找出哪個總權重最小，如果相同則留下字典序最小的
至於 DFS 的方向，因為考慮到字典序都是從前面判斷到後面，所以 DFS 方向也是從前到後應該比較直觀
每個方格經過 DFS 後就可以找到最小總權重，無論如何都不會改變，所以記得要把答案儲存起來，下次詢問就直接回答
定義 $dp[i][j]$ 表示第 $(i, j)$ 格向右走的最小總權重
則有轉移式
$$
dp[i][j] = min(dp[i-1][j+1], dp[i][j+1], dp[i+1][j+1])
$$
若 $i-1 < 0$ 則改為 $m-1$
若 $i+1 \geq m$ 則改為 $0$
並且
$$
dp[i][n-1] = arr[i][j] \quad 0 \leq i < m
$$
因為這題需要回朔路徑，需要紀錄每個點會轉移到下一行哪一列上
定義 $to[i][j]$ 表示 $(i, j)$ 轉移到 $j+1$ 行的哪一列
$$
to[x][y] = (nx, ny) \quad (dp[nx][ny] + arr[x][y] < dp[x][y] \texttt{ || } (dp[nx][ny] + arr[x][y] == dp[x][y] \texttt{ && } to[x][y] > nx))
$$
這裡以 buttom-up 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
const int MaxN = 2147483647;
int n, m, arr[15][105], dp[15][105], to[15][105];
int dx[3] = {-1, 0, 1};
int DFS(int x, int y){
if(dp[x][y] != MaxN)
return dp[x][y];
for(int i=0, nx, ny ; i<3 ; i++){
nx = x + dx[i];
ny = y + 1;
if(nx < 0) nx = m - 1;
else if(nx >= m) nx = 0;
int res = DFS(nx, ny) + arr[x][y];
// res 比當前紀錄答案還小
// 或是答案相同，但字典序可以更小
if(res < dp[x][y] || (res == dp[x][y] && to[x][y] > nx)){
dp[x][y] = res;
to[x][y] = nx;
}
}
return dp[x][y];
}
int main(){
while(cin>>m>>n){
// 初始化
for(int i=0 ; i<15 ; i++){
for(int j=0 ; j<105 ; j++){
dp[i][j] = MaxN;
to[i][j] = -1;
}
}
for(int i=0 ; i<m ; i++){
for(int j=0 ; j<n ; j++){
cin>>arr[i][j];
if(j == n-1)
dp[i][j] = arr[i][j];
}
}
// 因為可以保證起點的字典序只會越來越大，不必判斷 res==ans 的情況
int res, ans = MaxN, x, y=0;
for(int i=0 ; i<m ; i++){
res = DFS(i, 0);
if(res < ans){
ans = res;
x = i;
}
}
cout<<x+1;
while(to[x][y] != -1){
cout<<" "<<to[x][y]+1;
x = to[x][y];
y++;
}
cout<<"\n";
cout<<ans<<"\n";
}
return 0;
}
```
### 時間複雜度分析
每次轉移所需的時間複雜度為 $O(1)$
總共有 $n \times m$ 種狀態
每筆測資時間複雜度為 $O(nm)$
# UVa 10401
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10401
類似於八皇后問題，不過這次我們的皇后是受傷的皇后，攻擊範圍如下圖
黑色表示皇后所在的位置，而灰色表示可以攻擊的範圍
給定一個 $n \times n$ 的棋盤上，每一行的初始狀態，請問皇后有多少種放法，使得任意兩兩皇后之間不會互相攻擊到
初始狀態以一個長度 $n$ 的字串表示，其中 `?` 表示該行初始狀態沒有皇后
否則會以一個數字 $1$~$9$ 或是大寫英文字母 `A`~`Z` 表示該行皇后初始位於哪一列上
## 想法 By Koios
如果皇后要被放在 $(i, j)$ 上，那麼第 $i-1$ 行只有第 $0$~$j-2$ 列以及第 $j+2$~$n$ 列可以有皇后
也就是說只有這些點可以轉移到 $(i, j)$，所以只要將這些點的方法數加起來就會是 $(i, j)$ 的方法數
定義 $dp[i][j]$ 表示在前 $i$ 行，第 $i$ 行放皇后在 $(i, j)$ 的方法數
則有轉移式
$$
dp[i][j] = dp[i-1][k] \quad 0 \leq k \leq j-2 \texttt{ or } j+2 \leq k < n
$$
若第一行初始沒有任何皇后
$$
dp[0][k] = 1 \quad 0 \leq k \leq n-1
$$
若第一行有皇后位在 $(0, k)$
$$
dp[0][k] = 1
$$
以下以 Buttom-up 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
string s;
long long dp[20][20];
int to_int(char c){
if('1' <= c && c <= '9')
return c-'0'-1;
else if('A' <= c && c <= 'Z')
return c-'A' + 10-1;
}
int main(){
while(cin>>s){
// 初始化
for(int i=0 ; i<20 ; i++){
for(int j=0 ; j<20 ; j++){
dp[i][j] = 0;
}
}
// dp 初始值
if(s[0] == '?'){
for(int j=0 ; j<s.size() ; j++){
dp[0][j] ++;
}
}
else{
int tmp = to_int(s[0]);
dp[0][tmp] ++;
}
// 轉移
for(int i=1 ; i<s.size() ; i++){
if(s[i] == '?'){
for(int j=0 ; j<s.size() ; j++){
for(int k=0 ; k<=j-2 ; k++){
dp[i][j] += dp[i-1][k];
}
for(int k=j+2 ; k<s.size() ; k++){
dp[i][j] += dp[i-1][k];
}
}
}
else{
int j = to_int(s[i]);
for(int k=0 ; k<=j-2 ; k++){
dp[i][j] += dp[i-1][k];
}
for(int k=j+2 ; k<s.size() ; k++){
dp[i][j] += dp[i-1][k];
}
}
}
long long ans = 0;
for(int i=0 ; i<s.size() ; i++){
ans += dp[s.size()-1][i];
}
cout<<ans<<"\n";
}
return 0;
}
```
### 時間複雜度分析
輸入時間複雜度為 $O(n)$
DP 每個狀態轉移時間複雜度為 $O(n)$，總共有 $n$ 種狀態，DP 時間複雜度為 $O(n^3)$
計算答案時間複雜度為 $O(n)$
每筆測資總時間複雜度為 $2n + n^3$，計為 $O(n^3)$
# UVa 11258
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11258
給一個最長長度為 $200$ 的數字字串 $s$
你可以任意把 $s$ 切成好幾段子字串，但是任何一段的數值都不能超過 int 最大值 $2147483647$
請問切割出來後的數字總和最大可以是多少
## 想法 By Koios
如果枚舉每個切割點，時間複雜度大概是在 $n!$，顯然太慢
那麼我們慢慢從最後一個切割點來看
整個序列編號是從 $i$ 到 $j$，假設最後一次切割在 $k$ 點的位置
那麼題目就是在問能不能找到一個 $k$ 點，使得剩下的兩個子區間 $[i, k]$ 以及 $[k, j]$ 切割後的數值總和相加要是最大的
同樣的問題可以再推廣到這兩個之後的子序列
於是我們有個想法
定義 $dp[i][j]$ 表示區間 $[i, j]$ 切割後的最大數值總和
可以得到轉移式
$$
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j]) \quad i \leq k \leq j
$$
不過實際上這樣做還不夠快
仔細觀察一下轉移式會發現到，轉移時間複雜度約為 $O(n)$，而總共有 $n^2$ 種狀態，DP 時間複雜度約為 $O(n^3)$
再回到上一步重新思考一下要怎麼把一個 $n$ 壓掉
我們剛剛推得，最後題目在問的就是能不能找到一個 $k$，使得剩下的兩個子區間 $[i, k]$ 以及 $[k, j]$ 切割後的數值總和相加要是最大的
那麼如果想成後面的 $[k, j]$ 不要再切割呢?
也就是說，這一段就用剩下來的數字，但是要確保這段數字不會超過 $2147483647$
這樣剛剛的 $dp$ 式中 $dp[k][j]$ 就可以看做是一個常數
咦!剩下的只有 $max(dp[i][j], dp[i][k] + constant)$
發現到 $[i]$ 都是相同的
重新定義 $dp[i]$ 表示前 $i$ 個數字能切割出的最大數字總和
定義 $sum[i][j]$ 表示區間 $[i, j]$ 的數值，當超過 $2147483647$ 時為 $0$
$$
dp[i] = max(dp[i], dp[k] + sum[k+1][i]) \quad 0 \leq k < i
$$
初始值
$$
dp[i] = sum[0][i]
$$
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
const long long MaxN = 2147483647;
long long dp[205], sum[205][205];
string s;
int n;
int main(){
cin>>n;
while(n--){
for(int i=0 ; i<205 ; i++){
for(int j=0 ; j<205 ; j++){
sum[i][j] = 0;
}
}
cin>>s;
// 建立 sum 表格
for(int i=0 ; i<s.size() ; i++){
long long res = 0;
for(int j=i ; j<s.size() ; j++){
res = res * 10 + s[j] - '0';
if(res > MaxN) break;
sum[i][j] = res;
}
}
for(int i=0 ; i<s.size() ; i++){
dp[i] = sum[0][i];
for(int j=1 ; j<=i ; j++){
dp[i] = max(dp[i], dp[j-1] + sum[j][i]);
}
}
cout<<dp[s.size()-1]<<"\n";
}
return 0;
}
```
### 時間複雜度分析
令 $s$ 字串長度為 $n$
預處理時間複雜度為 $O(n^2)$
DP 每種狀態轉移時間複雜度為 $O(n)$，總共有 $n$ 種狀態，時間複雜度為 $O(n^2)$
每筆測資總時間複雜度為 $O(n^2)$
# UVa 10721
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10721
Bar-Code 是由很多亮/暗的 unit 組成，相同的顏色排在一起稱為一個 bar
$BC(n, k, m)$ 表示長度 $n$ 個 units ，並且由 $k$ 個 bar 組成，每個 bar 不超過 $m$ 個 units，並且第一個 unit 是黑色的 Bar-Code 個數
給定 $n, k, m$ ，求 $BC(n, k, m)$
## 想法 By Koios
對於每個 unit 我們都只有兩種選擇
1. 跟前面的 unit 組成 bar
2. 跟包括自己以後的組成 bar
從最後一個 unit 來看
- 如果選擇第一種，那麼問題就會變成詢問剩下的 $n-1$ 條 units 有 $k$ 個 bar ，而且最後一個 bar 不能超過 $m-1$ 個 units
- 如果選擇第二種，那麼問題就會變成詢問剩下的 $n-1$ 條 units 有 $k-1$ 個 bar，而且最後一個 bar 不能超過 $m$ 個 units
(會補上不能超過 $m$ 個 units 是為了讓問題跟第一種切出來的子問題相同)
發現到這兩個子問題跟母問題是一樣的，並且這兩個子問題的答案相家就會是母問題的解
定義 $dp[i][j][k]$ 表示 $i$ 個 units 有 $j$ 個 bar ，而且最後一個 bar 不能超過 $k$ 個 units 的 Bar-Code 共有多少種
則有轉移式
$$
dp[i][j][k] = dp[i-1][j][k-1] + dp[i-1][j-1][min(m, i-1)]
$$
會使用 $min(m, i-1)$ 是因為如果 $m$ 如果超過 $i-1$，那麼我們根本用不到 $m$ 那麼多，因為總長度也只有 $i-1$ 而已
並且因為要求第一條要是黑色，所以只有一個 bar 的時候只要長度 $i$ 小於等於限制 bar 的最大長度 $k$ 就有一個解
$$
dp[i][1][k] = 1 \quad i \leq k
$$
最後所有 $i, j, k$ 有任一個為 $0$ 都是沒有解的
$$
dp[i][j][k] = 0 \quad \texttt{i=0 || j=0 || k=0}
$$
以下以 Top-Down 實作
為了避免重複計算答案是 $0$ 的情況， $dp$ 初始值給不可能出現的 $-1$
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int N, K, M;
long long dp[55][55][55];
long long sol(int n, int k, int m){
if(n < 0 || k < 0 || m < 0) return 0;
if(dp[n][k][m] != -1) return dp[n][k][m];
return dp[n][k][m] = sol(n-1, k, m-1) + sol(n-1, k-1, min(M, n-1));
}
int main(){
while(cin>>N>>K>>M){
for(int i=0 ; i<=N ; i++){
for(int j=0 ; j<=K ; j++){
for(int k=0 ; k<=M ; k++){
if(i == 0 || k == 0 || j == 0)
dp[i][j][k] = 0;
else if(j == 1 && i <= k)
dp[i][j][k] = 1;
else
dp[i][j][k] = -1;
}
}
}
cout<<sol(N, K, M)<<"\n";
}
return 0;
}
```
### 時間複雜度分析
預處理時間複雜度為 $O(NKM)$
DP 轉移時間複雜度為 $O(1)$，總共有 $NKM$ 種狀態，DP 時間複雜度為 $O(NKM)$
每筆測資總時間複雜度為 $O(NKM)$
# TOJ 416
## 題目
https://toj.tfcis.org/oj/pro/416/
你的魔力超級強大，可以輕鬆燒光敵軍，
但你的愛杖『超級智慧魔杖』（簡稱超智杖）卻承受不住你的全力。
你能施展火球術、超炎爆術、以及超大型魔法隕石術三種。
火球術不論施展幾次都沒問題，但超炎爆術只能連續使用兩次。
連續使用三次的話，超智杖就會過熱而毀損。
但只要中間隔一回合冷卻，就能夠再連續使用兩次。
而隕石術由於消耗魔力過大，對超智杖負荷太重，只能使用一次，
不管經過多少回合，只要再次使用，超智杖就會承受不住而折斷。
如果要施展 $n$ 回合的法術，你會有多少種不同的方式可以燒掉敵軍?
## 想法1 (60%) By Koios
我們可以發現到火球術要在甚麼時候施展都無所謂，我們在意的只有會影響未來發展的超炎爆術以及隕石術
我們可以分成 $6$ 種狀態來討論
1. 連續施展超炎爆術 $0$ 次 ; 施展過隕石術 $0$ 次
2. 連續施展超炎爆術 $0$ 次 ; 施展過隕石術 $1$ 次
3. 連續施展超炎爆術 $1$ 次 ; 施展過隕石術 $0$ 次
4. 連續施展超炎爆術 $1$ 次 ; 施展過隕石術 $1$ 次
5. 連續施展超炎爆術 $2$ 次 ; 施展過隕石術 $0$ 次
6. 連續施展超炎爆術 $2$ 次 ; 施展過隕石術 $1$ 次
定義 $dp[i][j][k]$ 表示在第 $i$ 回合最後連續施展 $j$ 次超炎爆術，並且過去施展過隕石術 $k$ 次的方法數
$$
\begin{cases}
dp[i][0][0] = dp[i-1][0][0] + dp[i-1][1][0] + dp[i-1][2][0] \\
dp[i][0][1] = dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][2][0] + dp[i-1][2][1] \\
dp[i][1][0] = dp[i-1][0][0] \\
dp[i][1][1] = dp[i-1][0][1] \\
dp[i][2][0] = dp[i-1][1][0] \\
dp[i][2][1] = dp[i-1][1][1]
\end{cases}
$$
並且
$$
dp[0][0][0] = dp[0][0][1] = dp[0][1][0] = 1
$$
以下以 Buttom-up 實作
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int n;
long long dp[2][3][2];
const int Mod = 1000000007;
int main(){
while(cin>>n){
for(int i=0 ; i<2 ; i++){
for(int j=0 ; j<3 ; j++){
for(int k=0 ; k<2 ; k++){
dp[i][j][k] = 0;
}
}
}
dp[0][0][0] = dp[0][1][0] = dp[0][0][1] = 1;
for(int i=1 ; i<n ; i++){
for(int j=0 ; j<3 ; j++){
for(int k=0 ; k<2 ; k++){
dp[i%2][j][k] = 0;
}
}
// 火球術
for(int j=0 ; j<3 ; j++){
for(int k=0 ; k<2 ; k++){
dp[i%2][0][k] += dp[(i-1)%2][j][k];
dp[i%2][0][k] %= Mod;
}
}
// 爆炎術
for(int j=1 ; j<3 ; j++){
for(int k=0 ; k<2 ; k++){
dp[i%2][j][k] += dp[(i-1)%2][j-1][k];
dp[i%2][j][k] %= Mod;
}
}
// 隕石術
for(int j=0 ; j<3 ; j++){
dp[i%2][0][1] += dp[(i-1)%2][j][0];
dp[i%2][0][1] %= Mod;
}
}
long long ans=0;
for(int i=0 ; i<3 ; i++){
for(int j=0 ; j<2 ; j++){
ans += dp[(n-1)%2][i][j];
ans %= Mod;
}
}
cout<<ans<<'\n';
}
return 0;
}
```
### 時間複雜度分析
DP 每個狀態轉移時間複雜度可以視為 $O(1)$
總共有 $6n$ 種狀態，DP 時間複雜度計為 $O(n)$
但是在這題， $O(n)$ 還不夠快
:::info
100% 作法請參閱 `SCIST 演算法題解 - 動態規劃: 轉移矩陣`
:::
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet