# 單元七 動態規劃（Dynamic Programming）
## 簡介
動態規劃（Dynamic Programming, DP），是常用的一種解題方式，透過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法，從而提高算法效率，通常用於優化問題。

連結上一章講義提到的分治演算法，動態規劃正是其延伸。當分治法分割出來的問題，一而再、再而三出現，就運用記憶法儲存這些問題的答案，避免重複求解，以空間換取時間。

## 原理
在動態規劃中，我們首先需要明確**定義問題的狀態**。**狀態**是指問題在某個特定時刻或特定條件下所處的情況或位置。將問題划分成不同的狀態有助於我們將問題分解成較小的子問題。
而在進行動態規劃時，我們通常會依這個步驟進行：
**1、找出子問題**：將原問題分解成不同的子問題。
**2、確定狀態轉移關係**：找出問題和子問題之間的轉移關係，即如何由已知的狀態得到下一個狀態。
**3、找出子問題的計算順序**：確定子問題的計算順序，以避免不必要的重複計算。

## 狀態轉移
狀態轉移描述了**問題的不同狀態之間的轉移關係**。它表示了如何根據已知的狀態得到下一個狀態，以及這些狀態之間的相關性。
通常情況下，狀態轉移可以通過遞歸地定義來表示，將子問題看成不同狀態，而目前的狀態是根據之前的狀態轉移所得。

**EX、小朋友上樓梯**
假設今天有樓梯，一次跨兩階或一階，想要知道可以有幾種走法，可以從最後一階開始看，從最後一階回去找上一階和上兩階的方法加起來，所以我們就可以知道n階的方法是n-1和n-2加起來，就可以得到這個遞迴關係式。是不是覺得似曾相識？這就是我們之前在遞迴單元練習過的費式數列。與遞迴不同的是，DP會記錄子問題的解答。


## 種類
### Bottom-up
#### 簡介
Bottom-Up 從最小的子問題開始，逐步擴展到更大的問題，直到解決整個問題。它通常不使用遞迴，而是使用**迭代**從最小的子問題開始遞推到目標問題。它節省了遞迴所需要的時間複雜度，並且更容易理解和實現。
#### 優點
**1、避免了遞迴帶來的額外開銷**：此方法通常不使用遞迴，而是使用迴圈逐步計算子問題的解，因此避免了遞迴調用帶來的額外開銷。
**2、易於理解和實現**：過程中直接按照子問題的大小逐步擴展到目標問題，因此更容易理解和實現。
**3、不必擔心報錯**：沒有深度及遞迴的限制，因此不用擔心報錯的問題。

#### 缺點
**1、步驟較為繁瑣**：需要將遞迴關係式找出順序後，轉成迴圈
**2、無法避免不必要的計算**：Bottom-Up 方法可能計算出一些在實際求解中並不需要的子問題的解，因為它是從最小的子問題一直計算到目標問題。
#### 實作
以費式數列為例，以下是以 Bottom - Up 實現的方法：

#include <iostream>
#include <vector>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    // 建立一個大小為 n+1 的vector來儲存計算結果
    vector<int> dp(n + 1);

    // 初始化前兩項
    dp[0] = 0;
    dp[1] = 1;

    // 使用迴圈從底部開始計算到第 n 項
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // 返回第 n 項的結果
    return dp[n];
}

int main() {
    int n;
    std::cout << "輸入費式數列的項數: ";
    std::cin >> n;

    // 計算費式數列第 n 項
    int result = fibonacci(n);

    std::cout << "費式數列第 " << n << " 項的值是: " << result << std::endl;

    return 0;
}

### Top-Down
#### 簡介
Top-Down 方法從原始問題開始，通過記錄已解決的子問題的解，避免重複計算。它利用了遞迴的特性，並將子問題的解存儲在記憶體中，以便之後直接訪問。
#### 優點
**1、步驟較為簡單**：可以直接按照遞迴關係式計算。
**2、僅計算必要的子問題**：過程僅計算實際需要的子問題的解，因此可以節省計算資源。
**3、不必斤斤計較計算順序**：因為程式碼中的遞迴結構會迫使最小的問題先被計算
#### 缺點
**1、容易有報錯情況**：遞迴有成本與限制，不能超過一定的深度，因此在特定狀況下會導致報錯。
**2、記憶體空間運用較差**：無法自由地控制計算順序，因而無法妥善運用記憶體，浪費了可回收再利用的記憶體。
#### 實作
同樣以費式數列為例，以下是以 Top - Down 實現的方法：

#include <iostream>
#include <vector>
using namespace std;

// 遞迴計算費式數列
int fibonacci(int n, vector<int> &memo) {
    if (n <= 1) {
        return n;
    }

    // 如果已經計算過，就直接返回儲存的結果
    if (memo[n] != -1) {
        return memo[n];
    }

    //計算並儲存到vector中
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

int main() {
    int n;
    cout << "輸入費式數列的項數: ";
    cin >> n;
    
     // 建立一個大小為 n+1 的vector來儲存計算結果
    vector<int> memo(n + 1, -1);

    // 計算費式數列第 n 項
    int result = fibonacci(n, memo);

    cout << "費式數列第 " << n << " 項的值是: " << result << endl;

    return 0;
}

## 實戰演練
### 題目
#### a532. 奇特的數列

:::spoiler Hint：
### 解題想法
這個數列有一些規律，其中每一項都是「鏡像數」，即旋轉180度後的數仍相同。而這些數皆由數字 0, 1, 8, 6, 9 組成。
我們可以將已經生成的鏡像數儲存於數列中，並通過構造新的鏡像數來延續這個數列。並將新生成的每個鏡像數儲存，並使用已儲存的數列來查詢第 𝑁 項的值。
:::

:::spoiler Ans：

#include <string>
using namespace std;

int pointer = 7;
string sequence[1000005] = { "0", "1", "8", "11", "69", "88", "96" };

void Initialize() {
	int left = 3, right = 7, buffer, length = 3;
	while (pointer < 1000000) {
		if (length & 1) {
			for (int i = left; i < right && pointer < 1000000; i++) {
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + '0' + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + '1' + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + '8' + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
			}
		}
		else {
			buffer = pointer;
			for (int i = left; i < right && pointer < 1000000; i++) {
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + "00" + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + "11" + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + "69" + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + "88" + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
				sequence[pointer] = sequence[i].substr(0, sequence[i].size() >> 1) + "96" + sequence[i].substr(sequence[i].size() >> 1, sequence[i].size()), pointer++;
			}
			left = buffer, right = pointer;
		}
		length++;
	}
}

int main() {
	cin.sync_with_stdio(false), cin.tie(0);
	int number;
	Initialize();
	while (cin >> number, number) 
		cout << sequence[number - 1] << '\n';
}

//解法參考：https://zerojudge.tw/ShowProblem?problemid=a532

:::

## 結語
動態規劃是一種較有效率的問題解決方法，通過將原問題分解為相對簡單的子問題並妥善地組織和計算這些子問題的解，能夠有效地提高算法效率。在解決實際問題時，我們需要根據問題的特性和要求選擇適合的動態規劃方法以及相應的優化策略，以確保算法的效率和準確性。