# APCS初心者講義
## 編者主頁:arrow_right:[Yun](https://www.instagram.com/y._.05.27/)
:::spoiler 目錄
[toc]
:::
## 其他學習連結
* [實作考古題](https://hackmd.io/@Yunn0527/HJUTcgUZR)
* [要拼三級再看（二維陣列）](https://hackmd.io/@Yunn0527/ryK5EWrZ0)
* [觀念練習題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2022/10/%E8%A7%80%E5%BF%B5%E9%A1%8C_%E9%A1%8C%E5%9E%8B%E7%AF%84%E4%BE%8B.pdf)
# if else 判斷式之類的
## 比較運算
### 比較運算子
- `>` 大於
- `>=`大於等於
- `<` 小於
- `<=` 小於等於
- `==` 判斷是否相等
- `!=` 不等於
■ 範例：不要用等號判斷浮點數
```cpp=
double a = 0.1;
double b = 0.2;
cout << (a+b==0.3);
```
結果：
```
0
```
■ 範例：
```cpp=
cout << (5>=2) + (5<=2) + (5==2) + (5!=2);
```
結果：
```
2
```
■ 範例：判斷奇偶數
`(x%2) == 0` 如過是對的，表示 `x` 是偶數
`(x%2) != 0` 或 `!(x%2)` 是對的，表示 `x` 是奇數
## 邏輯運算
### 邏輯運算子
- 邏輯AND: `and` 或 `&&`
- 邏輯OR: `or` 或 `||`
- 邏輯NOT: `not` 或 `!`
這表應該蠻好用的(吧?)
| && | true | false |
|:-----:| -------- | ----- |
| true | **true** | false |
| false | false | false |
| \|\| | true | false |
|:-----:| ---- | --------- |
| true | true | true |
| false | true | **false** |
| | ! |
| ----- |:-----:|
| true | false |
| false | true |
:::info
and要大家都 true 他才 true，
or要大家都 false 他才 false，
not 則相反，你 true 他就 false
:::
■ 範例
```cpp=
int x = 5, y = 2, z = 3;
bool A = (x<y);
bool B = (z!=y);
cout << A << endl;
cout << B << endl;
cout << (A && B) << endl;
cout << (A || B) << endl;
cout << (!A);
```
結果：
```
0
1
0
1
1
```
■ 範例
給 3 科成績，請判斷 a) ALL Pass; b) 幾科不及格 c) 總平均超過88分
```cpp=
int a, b, c;
cin >> a >> b >> c;
cout << (a>=60 && b>=60 && c>=60) << endl;
cout << (a<60) + (b<60) + (c<60) << endl;
cout << ((a+b+c)/3>88);
```
■ 範例：字元判斷
- 若 `c` 為大寫字母，則 `c>='A' && c<='Z'` 為真
- 若 `c` 為小寫字母，則 `c>='a' && c<='z'` 為真
- 若 `c` 為數字，則 `c>='0' && c<='9'` 為真
■ 範例
A)
```cpp=
int a=1;
if (a==2) cout << "A\n";
cout << "B\n";
cout << a;
```
結果：
```
B
1
```
B)
```cpp=
int a=1;
if (a+=2) cout << "A\n";
cout << "B\n";
cout << a;
```
結果：
```
A
B
3
```
C)
```cpp=
int a=1;
if (a=2) cout << "A\n";
cout << "B\n";
cout << a;
```
結果：
```
A
B
2
```
### 多向判斷
```cpp=
if (A) {
block1;
} else if (B) {
block2;
} else if (C) {
block3;
} else {
block4;
}
```
■ 範例
請指出以下程式哪句是多:fish:的(永遠執行不到)。
```cpp=
int n;
cin >> n;
if (n%2==0) cout << "被2整除";
else if (n%3==0) cout << "被3整除";
else if (n%4==0) cout << "被4整除";
else if (n%5==0) cout << "被5整除";
else cout << "不被2,3,4,5整除";
```
答案：
第5行 `else if (n%4==0) cout << "被4整除";`
### 巢狀判斷
```cpp=
if (A) {
if (B) {
block2;
}
block1;
}
```
A and B 為 true 執行 block1 與 block 2;
A 為 true B 為 false 執行 block1;
A 為 false 不執行 block1 與 block2。
寫巢狀判斷要把優先的判斷式寫在外面。
**講ez點就是外面判斷完換裡面 順序很重要**
■ 範例：判斷倍數
給數字 a, b，判斷 a 是否為 b 的倍數。
```cpp=
int a, b;
cin >> a >> b;
if (a%b==0) cout << "Yes";
```
■ 範例：閏年判斷
滿足以下兩個條件之一即為閏年：
```cpp=
if ((y%4==0) && (y%100!=0) || (y%400==0))
cout << "閏年";
else
cout << "平年";
```
以下是相同結果的程式：
```cpp=
if (y%400==0)
cout << "閏年";
else if (y%4==0)
cout << "閏年";
else
cout << "平年";
```
■ 範例
輸入一個字元c，判斷c是大寫字母、小寫字母、數字或者其他符號。
```cpp=
char c;
cin >> c;
if (c>='a' and c<='z') cout << "lower case";
else if (c>='A' and c<='Z') cout << "upper case";
else if (c>='0' and c<='9') cout << "number";
else cout << "other";
```
注意寫成以下程式碼是==錯的==：
```cpp=
if ('a'<=c<='z') cout << "lower case\n";
else if ('A'<=c<='Z') cout << "upper case\n";
else if ('0'<=c<='9') cout << "number\n";
else cout << "other\n";
```
■ 範例
輸入若為 4 或 13，輸出 "bad luck"；
輸入若不是 4 或 13，輸出 "good luck"
```cpp=
int n;
cin >> n;
if (n==4)
cout << "bad luck";
else if (n==13)
cout << "bad luck";
else
cout << "good luck";
```
```cpp=
if (n==4 or n==13)
cout << "bad luck";
else
cout << "good luck";
```
```cpp=
if (not(n==4 or n==13))
cout << "good luck";
else
cout << "bad luck";
```
--------------------------------
# 迴圈
## 學習目標
- 活著
## 遞增/遞減運算子
遞增：
- `x++`
- `++x`
遞減：
- `x--`
- `--x`
- 阿記得在for迴圈的最後一個不要加;
■ 範例
```cpp=
int y = 1;
cout << y << '\n';
cout << y++ << '\n';
cout << y << '\n';
cout << ++y << '\n';
cout << y << '\n';
```
:::spoiler 結果
```
1
1
2
3
3
```
:::
■ 範例
```cpp=
int x = 0, y = 0;
cout << ++x << " " << y++ << endl;
cout << x++ << " " << ++y << endl;
```
:::spoiler 結果
```
1 0
1 2
```
:::
:::info
記一下這個：
在變數前，先做增減；
在變數後，後做增減。
:::
## 迴圈
### for 跟while
## for 迴圈
基本語法：
```
for (初始敘述; 檢查條件; 計量敘述) {
// 每次迴圈要執行的敘述
}
```
- for() 裡的敘述用分號`;`分隔，共有==2個分號==
- 初始敘述是設定初始值，就像設定最一開始的起點
- 檢查條件是設定結束值 我都叫他終止點，如果沒達到就繼續執行迴圈
- 計量敘述是讓計數變數遞增或遞減，最終讓變數達到結束值 (ex:i++)
- 迴圈如果設置不對，就永遠不會結束 (ex:你終止值比初始值大，然後記量敘述遞減:arrow_right: for(int i = 0;i < 5;i - -) )
■ 範例：
重複100次的for迴圈寫法。
```cpp=
for(int i=0; i<100; i++){
cout <<"Yun is clever" << endl;
}
```
■ 範例：計算級數和或階乘。
```cpp=
int n = 0;
for(int i=1; i<=10; i++){
n += i;
}
cout << n << endl;
int m = 1;
for(int i=1; i<=10; i++){
m *= i;
}
cout << m << endl;
```
■ 範例：
for 迴圈變數的一些概念。
```cpp=
int j = 0;
for(int i=0; i<10; i++){
j+=i;
}
cout << i << " " << j;
```
請問~~Yun~~ 程式錯哪了:cry: ?
:::spoiler 說明
變數 i 只在 for 迴圈裡面有效。
所以在for外面cout沒用。
:::
```cpp=
int i, j=0;
for(i = 0; i<10; i++){
j+=i;
}
cout << i << " " << j;
```
執行結果：
```
10 45
```
■ 範例：
輸出小於 N 的奇數。
```cpp=
int n;
cin >> n;
for(int i=1; i<n; i+=2){
cout << i << " ";
}
```
輸出小於 N 的偶數。
```cpp=
int n;
cin >> n;
for(int i=0; i<n; i+=2){
cout << i << " ";
}
```
■ 範例：輸出因數。
```cpp=
int n;
cin >> n;
for(int i=1; i<=n; i++){
if (n%i==0) { // 整除
cout << i << " ";
}
}
```
■ 範例：讀入多筆測資。
輸入: 第一行是測資個數 n，第二行開始有 n 行，輸入西元年。
輸出: 輸出 n 行，若第 i 個西元年是閏年，輸出 Yes，否則輸出 No。
```cpp=
int t;
cin >> t;
for(int i=0; i<t; i++){
int y;
cin >> y;
if(((y%4==0)&&(y%100!=0))||(y%400==0))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
```
## while 迴圈
基本語法：
```cpp=
while(檢查條件)
{
執行敘述;
調整敘述;
}
```
看一下：
條件成立就一直執行，直到不成立為止
當檢查條件不是 False (或 0)時，while 迴圈會一直執行，就上次說的那個無窮迴圈。下面 3 個是無窮迴圈的範例：
```cpp=
while(1){}
while(!0) {}
while(999) {}
```
如果檢查條件是 False，while 迴圈會直接結束，例如：
```cpp!
while(0) {}
```
下面兩個例子都是一直列印 Hello 字串：
(A)
```cpp!
while(cout << "Hello" << endl) {}
```
(B)
```cpp!
while(1) {cout <<"Hello" << endl;}
```
▲沒盡頭，還是一直做，徒勞無功(就跟Yun暈她一樣嗚嗚嗚嗚嗚嗚😭😭)
■ 範例：
輸入一堆數字，找出最小值與最大值。
輸入: 第一行輸入數字個數 n，第二行輸入 n 個整數。
輸出: 輸出最大值與最小值。
```cpp!
int n, num;
cin >> n;
int minNum = 9999999;
int maxNum = -9999999;
while(n--){
cin >> num;
if (num<minNum) minNum = num;
if (num>maxNum) maxNum = num;
}
cout << maxNum << " " << minNum;
```
:::spoiler 參考解答
```cpp=
int n, num, minNum, maxNum;
cin >> n;
cin >> num;
minNum = maxNum = num;
for (int i = 0; i < n - 1; i++) {
cin >> num;
if (num < minNum)
minNum = num;
if (num > maxNum)
maxNum = num;
}
cout << minNum << " " << maxNum;
```
其中 for 改 while 的寫法:
```cpp=
while(--n){
cin >> num;
if (num < minNum)
minNum = num;
if (num > maxNum)
maxNum = num;
}
```
:::
■ 範例：
輸入多筆測資。
輸入: 輸入正整數 n，若 n = 0 結束。
輸出: 印出 n 個字元長度的 `*`。
```cpp=
int n;
while(cin>>n and n){
for(int i=0; i<n; i++)
cout << "*";
cout << endl;
}
```
這個 `while(cin>>n and n)`
可以理解成：
```
while(cin>>n and n!=0)
```
改 for 迴圈重寫。
```cpp=
int n;
cin >> n;
for( ;n!=0; cin>>n){
for(int i=0; i<n; i++)
cout << "*";
cout << endl;
}
```
■ 範例：
求1到100的總和。
```cpp=
int i=1, sum=0;
while(i++ <= 100){
sum += i;
}
cout << sum;
```
如果程式看不懂，可以拆成這樣：
```cpp=
int i=1, sum=0;
while(i <= 100){
sum += i;
i++;
}
cout << sum;
```
■ 範例：
取出整數的每一位數。
輸入: 輸入整數 n, 取出每一位數並加總，結果為 s。
輸出: 如果 s 可以整除 n，印出 Yes；否則印出 No。
※ 這題在[這裡](https://atcoder.jp/contests/abc101/tasks/abc101_b)
:::spoiler 參考解答
```cpp=
int n;
cin >> n;
int s = 0, temp = n;
while (temp) {
s += temp%10;
temp /= 10;
}
if (n % s == 0) {
cout << "Yes\n";
} else {
cout << "No\n";
}
```
:::
■ 範例
輾轉相除法。(我高一不會這數學 超嚴重 然後這個很重要 很長考到 以後遞迴也有)
輸入: 輸入兩個整數 x, y。
輸出: 印出 x 與 y 的最大公因數。
```cpp=
int x, y;
cin >> x >> y;
while(x%y !=0){
int temp = x%y;
x = y;
y = temp;
}
cout << y;
```
■ 範例
各種結束條件的例子。
1. 只讀 1 行：[d067](https://zerojudge.tw/ShowProblem?problemid=d067)。
```cpp=
int n;
cin >> n;
```
2. 讀進 n 行：[d069](https://zerojudge.tw/ShowProblem?problemid=d069)。
```cpp=
int n; cin >> n;
while(n--){
}
```
3. 當輸入值為特定值時結束：[d070](https://zerojudge.tw/ShowProblem?problemid=d070)。
```cpp=
int n;
while(cin>>n) {
if (n==x) break;
}
```
4. 遇到 EOF(End of File) 結束：[d071](https://zerojudge.tw/ShowProblem?problemid=d071)
```cpp=
int n;
while(cin>>n){
}
```
5. 每筆測資要顯示編號：[d072](https://zerojudge.tw/ShowProblem?problemid=d072)
```cpp=
int n, t=0;
cin>>n;
while(n--){
cout << "case " << ++t << ans;
}
```
## continue / break
- continue: 忽略後面的程式直接下一圈
- break: 直接離開迴圈
■ 範例
判斷質數。
```cpp=
int n;
while(cin>>n){
bool prime = true;
for(int i=2; i*i<=n; i++){
if (n%i==0) {
prime = false;
break;
}
}
if (prime)
cout << n << " is a prime.\n";
else
cout << n << " is not a prime.\n";
}
```
■ 範例
計算正整數的和
輸入: 輸入 n 個整數。
輸出: 計算其中的正數總和。
```cpp=
int n, num, sum=0;
cin >> n;
while(n--){
cin >> num;
if (num<0)
continue;
sum += num;
}
cout << sum;
```
不爽用 `continue`，可以改成這樣:
:::spoiler 參考程式
```cpp=
while(n--){
cin >> num;
if (num>0)
sum += num;
}
```
:::
-----
## 陣列
陣列(array)就是一串空間，每一節都可以儲存資料：
- 只能儲存相同型態的資料(就是你宣告的時候如是int，那整個陣列只能存int型態的東西)。
- 陣列名稱就是變數名稱。
- 陣列內每筆資料可以用索引值(index)存取，而索引值==從0開始==編號，依序是0, 1, 2, ...，依此類推(因此最後一個索引值為陣列大小減1)。
- 電腦是用==連續==的記憶體空間來儲存陣列。(通常不會考)
## 一維陣列
### 宣告
一維陣列只有一個索引，宣告方式如下：
```
type name[size];
```
說明：
- name 是陣列的名稱
- size 是陣列的大小，如果 size 是 n (n為正整數)，表示陣列內可以存 n 個元素
- type 是陣列元素的資料型態，ex: int, char
- 存取每個元素要使用 `name[index]`。
如上圖陣列 prime 有7個元素，以下的程式碼是給定每個位置值的方法
```cpp=
int prime[7];
prime[0] = 2, prime[1] = 3, prime[2] = 5, prime[3] = 7, prime[5] = 13, prime[6] = 17; // 給值
cout << prime[6] << endl; // 取值
```
上面給值的寫法是一個個元素指定初始值，但寫法比較 :chicken: 8 ，另一個比較ez，就是用大括號{ }依序存入各個位置的初始值，ex：
```cpp
int prime[7] = {2,3,5,7,11,13,17};
```
沒打大小也沒差，系統會自動給陣列大小，ex：
```cpp
int prime[] = {2,3,5,7,11,13,17};
```
然後就是如果陣列大小比元素的數量少，會編譯錯誤喔(overflow) :warning:
### 遍歷
走訪陣列所有元素，要小心陣列的索引值是從 0 開始，若大小為 n，則最後一個元素的索引值為 n-1(剛剛上面有講到的就是這個)。建議用 for 迴圈 來存陣列的每個元素，(我記得以前有一個神經病用while迴圈，然後程式寫不出來)
例如：
```cpp=
int a[5] = {1,3,5,7,9};
for(int i=0; i<5; i++) {
cout << a[i]-1 << " ";
}
```
輸出結果：
```
0 2 4 6 8
```
■ 範例
有時候題目希望我們cout迴圈時，最後一個元素後面不能出現空格，例如上面程式的結果：
```
0_2_4_6_8_
```
`_` 是空格，但題目希望輸出結果是：
```
0_2_4_6_8
```
有很多寫法，可以控制第一個元素和其它元素的輸出：
```cpp=
int a[5] = {1,3,5,7,9};
for(int i=0; i<5; i++) {
if (i==0)
cout << a[i]-1;
else
cout << " " << a[i]-1;
}
```
如果沒有考慮控制輸出結果，最簡單的遍歷方式應該是 C++ 的 range for:(這很好用，可是來不及學就算了)
```cpp=
for (auto element:array)
cout << element << " ";
```
這種寫法不用靠索引值來存取個別元素。
### 可變長度陣列
:warning: 注意不是陣列大小可以變，是可以在執行時才決定陣列大小 會常用到以下兩種函數:
- size()
- length()
(等等會講到)
■ 範例：反向輸出
輸入 n 個數字後，反向輸出數列。
輸入方式，先讀入數字 n，再讀入 n 個數字，結束時反向順序輸出該 n 個數字。(for迴圈的改變要活用)
```cpp=
int n;
cin >> n;
int a[n];
for(int i=0; i<n; i++)
cin >> a[i];
for(int i=n-1; i>=0; i--)
cout << a[i] << " ";
```
### 初始值
陣列如果宣告為全域變數，如果不指定初始值，就是0，但如果是區域變數，初始值不一定是0。
ex：陣列初始值
```cpp=
int a[100];
int main()
{
int b[100];
for(int i=0; i<100; i++) {
cout << a[i] << " ";
}
cout << "\n";
for(int i=0; i<100; i++) {
cout << b[i] << " ";
}
return 0;
}
```
a[] 在 main() 函數外，是全域變數，b[]是區域變數。
像這樣(亂七八糟)：
如果要設陣列初始值全部為 0，有兩種方式：
```cpp=
int a[10] = {};
// int a[10] = {0}; 另一種寫法(但沒必要)
for(int i=0; i<10; i++)
cout << a[i] << " ";
```
輸出結果：
```
0 0 0 0 0 0 0 0 0 0 0
```
但是這種寫法只可以全部都 0，不然你看這個：
```
int a[10] = {-1};
```
陣列 a 的內容應該是：
```
-1 0 0 0 0 0 0 0 0 0
```
如果要產生一個內容全部是 -1 的陣列，可以用迴圈：
```cpp=
int b[10];
for(int i=0; i<10; i++) {
b[i] = -1;
}
for(int i=0; i<10; i++) {
cout << b[i] << " ";
}
```
結果：
```
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
```
### 我犯過的白痴錯誤
索引值超過陣列的大小，編譯器不會靠邀你，然後結果你也不知道。
下面是錯：
```cpp=
int a[3] = {1,2,3};
cout << a[3];
```
陣列大小是 3, 最後一個元素的索引值為 其實是2(陣列大小-1), 想要列印最後一個元素用 a[3]，輸出結果是隨機的數字 。
## 字元陣列
string，反正我們不寫c，很爽不用學字元陣列，但是string 還是可以當陣列用
### 字元
char
#### 跳脫字元
常用的跳脫字元
反正如果字元被感應成程式碼，要把她單獨提出來用雙引號包住
#### 字元與整數轉換
字元如果要整數型態輸出，會顯示字元的ASCII數值(十進位)。
■ 範例
```cpp=
char c;
c = 'A';
cout << c << "'s ASCII code is "<< int(c);
```
結果：
```
A's ASCII code is 65
```
當我們字元與數值進行運算的時候，字元將以十進位的ASCII數值代表。
■ 範例
```cpp=
char c = 'A';
cout << c+10;
```
結果：
```
75
```
### 字元陣列宣告
字元陣列宣告語法：(這個看看就好，但觀念可能考)
```
char name[size]
```
其中
- `name` 是變數名稱
- `size` 是陣列大小，也就是字元數
字元陣列可以用字串當成初始值，ex：
```cpp=
char name[] = "Alice";
cout << "Hello, " <<name << endl;
```
結果：
```
Hello, Alice.
```
## 字串
C++支援一種名為 `string` 的資料型態，字串本質是特殊的字元陣列，這基本用法，進階用法以後會學到。(應該吧)
### 讀入字串
C++ 可以用 string 宣告一個變數，然後用 `cin` 或 `getline()` 輸入。
```cpp=
string name;
cin >> name;
cout << "Hello, " << name << ".";
```
這寫法不用設定字串長度。
但是，如果輸入的字串有空格、換行之類的，只有在空格前的字串會被讀入。
例如輸入 `John Wick`，上面的結果是 `Hello, John.`。
### 讀入整行文字
用 `getline(cin, string)` 可以讀入整行字串(包含空白字元)。(建議有空白再用就好)
■ 範例：計算單字數。
```cpp=
string line;
getline(cin,line);
int cnt = 0;
for(int i=0; i<line.size(); i++) {
if (line[i]==' ') {
continue; // 遇到空格跳過
} else {
if (i==0 or line[i-1]==' ') cnt++; // 避免第一個字元是空格
}
}
cout << cnt <<endl;
```
■ 範例：反向輸出字串。
```cpp=
string s;
cin >> s;
for(int i=s.size(); i>=0; i--)
cout << s[i];
```
用 `s.size()` 得到字串長度，並用 for 迴圈 從尾端遍歷字串。另一個函數 `s.length()` 可以得到字串長度。
■ 範例：首字大寫。
將字串的第一個字元改為大寫。
```cpp=
string s;
getline(cin,s);
cout << s << endl;
if (0<= s[0]-'a' < 26) {
s[0] = 'A'+(s[0]-'a');
}
cout << s << endl;
```
先用小寫字元減去'a'將是0-25的整數這個技巧，判斷首字是否為小寫，再把它轉為大寫字母。
當然，第5-7行的程式，可以用 `s[0] = toupper(s[0]);` 直接轉換。(其實還有一堆函式，只是我怕太多有人可能受不了)
◼ 範例：凱薩加密。
凱薩密碼是一種位移加密的密碼技術，維基百科[說明](https://zh.wikipedia.org/zh-tw/%E5%87%B1%E6%92%92%E5%AF%86%E7%A2%BC)。
為了避免輸入字串有大小寫的字元，可以都轉換為大寫再進行轉換。
```cpp=
int k = 3; // 假設位移量是 3
string s;
getline(cin,s);
for(int i=0; i<s.size(); i++)
s[i] = toupper(s[i]); // 轉換為大寫
for(int i=0; i<s.size(); i++)
if (isupper(s[i])) {
s[i] = 'A'+(s[i]-'A'+k)%26;
cout << s;
```
---
# 低批
## dynamic programming
## 基本思維
DP有點像進階的分治法：(我對他最大的第一印象是以空間換取時間喔)
1. 定義子問題。
2. 找出問題與子問題之間的(遞迴)關係。
3. 找出子問題的計算順序，避免以遞迴的方式進行計算。
DP 在步驟3用建立表格計算的方式，以克服分治法遞迴深度太深的缺點。適合 DP 的問題具有重疊的子問題和最優子結構等2種性質：
- 重疊子問題(Overlapping Subproblems)：相同的子問題會在運算中反覆出現。
- 最優子結構（Optimal Substructure）：如果一個問題的解，對於子問題也是最佳解，稱該問題有最優子結構特性。
## 動態規劃與分治法
以費氏數列(Fibonacci Sequence)為例。費氏數列為0,1,1,2,3,5,8,13,21,34,....，其定義為：
$\left\{
\begin{array}{l}
F_0=0 \\
F_1=1 \\
F_n=F_{n-2}+F_{n-1}, n \ge 2
\end{array}
\right.$
根據定義可以寫出遞迴函式如下：
```cpp=
int f(int n)
{
if (n==0||n==1) return n;
return f(n-2)+f(n-1);
}
```
如果 n = 7，那麼呼叫情形如下圖所示：
<small>圖源: https://zetria.tw/python/7d9a471162</small>
可以看到隨著n愈來愈大，函式呼叫次數也愈來愈多。
寫一個程式來觀察：
```cpp=
int times;
int f(int n)
{
times++;
if (n==0||n==1) return n;
return f(n-2)+f(n-1);
}
int main()
{
int n;
while(cin>>n&&n>=0) {
times=0;
f(n);
cout << times-1 << "\n";
}
return 0;
}
```
現在改用表格紀錄的方式來改善重複呼叫的問題。
```cpp=
vector<int> mem;
int fib(int n)
{
if (n==0||n==1) return n;
if (mem[n]!=0) return mem[n];
mem[n]=fib(n-1)+fib(n-2);
return mem[n];
}
int main()
{
int n;
cin>>n;
mem.resize(n+1);
cout << fib(n);
return 0;
}
```
為了感受速度差異，可以用 $n=45$ 試試看兩種不同實作的執行速度。
這種用表格記錄遞迴結果的技術稱為記憶化(Memorization)，但本質還是Top-Down的思路，算是遞迴的加速方法。
:::success
**Top-Down Memorization**
遞迴加上查表的作法。技巧是用表格記錄每次計算結果，初始值是某個不可能的值，以辨識未曾算過。在遞迴之前，先查表，若表格有資料，直接回傳答案；若表格無資料，則遞迴呼叫，但==呼叫前先記錄==。
:::
接著考慮 DP 思維：Bottom-Up，只要讓遞迴式右邊出現在左邊之前先計算，然後用表格把結果記錄下來，就不需要遞迴了。以遞迴式$f(n)=f(n-1)+f(n-2)$為例，如果計算到$f(n)$之前，$f(n-1)$與$f(n-2)$均已計算過，直接從表格取出$f(n-2)$與$f(n-1)$並相加，就可以得到$f(n)$。
範例如下：
```cpp=
int fib(int n)
{
vector<int> v(n+1);
v[1]=1;
for(int i=2; i<=n; i++)
v[i]=v[i-1]+v[i-2];
return v[n];
}
```
總結一下 DP 的解題步驟：
1. 定義子問題
2. 尋找遞迴關係
3. 尋找計算順序，避免使用遞迴
DP 的程式幾乎都是用迴圈處理表格，程式本身不難，難的是怎麼找遞迴關係，這可以靠多做題目培養經驗來加強解題能力。
## 爬樓梯問題
出處：[ZeroJudge c547](https://zerojudge.tw/ShowProblem?problemid=c547)
### 說明
BERT 是個奇怪的人，爬樓梯都不乖乖的一次走一格，而是有時走一階，或一次走兩階。
假設階梯有三階，那他有三種走法，如下：
一： 第一步走一階，第二步走二階。
二： 第一步走二階，第二步走一階。
三： 全程都走一階。
### 輸入
多筆輸入
每行一個數字 N ，代表現在有 N 階樓梯 。
(1 <= Ｎ <= 10000)
### 輸出
每行一個數字，代表當樓梯有 N 階時的答案。
答案可能很大，請 mod 1000000007
### 範例
```
輸入
3
1
輸出
3
1
```
### 思路
第一步，定義子問題。令 $f(i)$ 表示走到第 $i$ 階的走法數。
第二步，找出遞迴關係。走到第 $n$ 階時，前一個狀態一定是 $f(n-1)$ 或 $f(n-2)$，也就是 $f(n)=f(n-1)+f(n-2)$
又 $f(1)=1, f(2)=2$。
完整的遞迴關係式如下：
$$
f(n) = \left\{
\begin{array}{ll}
f(n-1)+f(n-2),\quad &\mbox{if $n>2$} \\
n, &\mbox{otherwise}
\end{array}
\right.
$$
■ 遞迴版本：
```cpp=
long long stair(int n) {
if (n<3) return n;
return stair(n-1)+stair(n-2);
}
```
這個遞迴呼叫的方式非常消耗資源，因為一次遞迴執行兩次函數呼叫，時間複雜度趨近於 $O(2^n)$。
現在來看第三步驟，找出計算順序避免遞迴方式計算。這裡的技巧是只要讓遞迴式等號右邊先算，並且用表格把計算結果記錄下來。令 $n$ 是從小到大計算，計算到 $f(n)$ 時，直接查表就可以得到 $f(n-1)+f(n-2)$。
我們可以用一個陣列 `S[i]` 來儲存 `f(i)` 的計算結果。
■ DP 版本
```cpp=
long long S[10001]; // 儲存樓梯走法
int n; // 樓梯階數
while(cin >> n)
{
S[1]=1, S[2]=2;
for (int i=3; i<=n; i++)
S[i] = (S[i-1] + S[i-2]) % 1000000007;
cout << S[n] << endl;
}
```
以上過程只是展示如何尋找遞迴關係，進而尋找計算順序的解題過程。熟悉的人應該一眼就看出是費氏數列。
## Bee
題目：[UVa 11000 - Bee](https://zerojudge.tw/ShowProblem?problemid=d261)
:::info
2022-05-24 CPE #2
:::
每年母蜂生一隻公蜂，然後每年公蜂生一隻公蜂與一隻母蜂，第一隻母蜂永遠不死。問第N年公蜂的數量以及所有蜜蜂的數量。
先找遞迴關係式：
$\left\{
\begin{array}{l}
F_0=1 \\
M_0=0 \\
F_n=M_{n-1}+1 \\
M_n=F_{n-1}+M_{n-1}
\end{array}
\right.$
記得要用 `long long` 來計算。
:::spoiler 參考程式
```cpp=
typedef pair<long long, long long> pll;
typedef vector<long long> vll;
pll f(int n)
{
vll male(n+1);
vll female(n+1);
female[0]=1;
for (int i=1; i<=n; i++) {
female[i]=1+male[i-1];
male[i]=female[i-1]+male[i-1];
}
return make_pair(male[n],male[n]+female[n]);
}
int main()
{
int n;
while(cin>>n&&n!=-1) {
pll ans=f(n);
cout << ans.first << " " << ans.second << "\n";
}
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet