---
title: 'C++ 動態規劃（DP）基礎入門'
disqus: hackmd
---

# 前言

動態規劃（Dynamic Programming, DP）是競賽和程式解題裡很常見、很重要的技巧，尤其是遇到「重複子問題」、「每一項要靠前面結果才能推出來」這種題目的時候。

同時如果有人想在下學期加入進階班，我們二篩會出一題基礎的 DP 題，這講義會被生出來也是希望大家有個東西可以看一下。

如果我有編錯或編爛的部分請見諒，然後趕快告訴我。

---

# 什麼是 DP？

DP 的核心想法就是「把每個已經算過的子問題答案記下來，下次要用直接拿，避免重複運算」。
但重點不只是這樣，**DP 特別適用於「後面的狀態/答案會受前面影響」的問題**。
你可以想像：每一個階段的答案都要參考之前某些階段的結果，這樣一個一個慢慢推下去。

典型特徵有：
- 問題可以拆成小塊，每一塊的答案對後面的計算有影響
- 小問題會重複出現
- 狀態之間有明確的遞推（前一項/幾項影響後一項）

---

# DP 解題思路

1. **狀態定義**
先思考 dp[i] 代表什麼意思（例如「前 i 天的最大收益」或「長度為 i 的答案有幾種」）。
2. **狀態轉移**
也可說是轉移式
是 DP 最重要的地方(至少我個人認為)
狀態轉移式（也叫遞推式、轉移方程式）就是「現在這個狀態，怎麼用前面已經算好的狀態組合出來」。你可以把它想成是「前項怎麼影響後項」的公式。 (現在覺得抽象沒關係，後面的例題會提到)
大部分 DP 的難點都卡在這裡，通常要多列幾個小樣本出來找規律。
3. **初始值（Base Case）**
把最基礎的狀況手動設定好，讓後面可以正常推下去。
4. **依序計算出所有狀態**
通常用 for 迴圈，照順序把 dp 填完。

**現在可能會聽的很疑惑，但帶入例題後應該會更好理解**

---

# 經典例題：費波那契數列

## 題目
算 F(n)，其中 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

---

## 最原始的寫法（暴力遞迴）

int fib(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

這種寫法很直覺，但 n 稍微大一點（例如 40）就會很慢，因為同一個 subproblem（像 fib(5)）會被重複計算很多次。

那要怎麼改善?
還記得前面提到的嗎? DP 的核心想法就是「把每個已經算過的子問題答案記下來，下次要用直接拿，避免重複運算」。
所以我們可以把每次計算出來的答案開一個陣列存下來，可以有效增加運行速度。

---

## DP 寫法（自底向上）

### 狀態定義
- dp[i] 表示 F(i) 的值

### 狀態轉移
- dp[i] = dp[i-1] + dp[i-2]
（也就是第 i 項要靠前兩項的結果）

### 初始值
- dp[0] = 0
- dp[1] = 1

### Code 範例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> dp(n+1);
    dp[0] = 0;
    if (n >= 1) dp[1] = 1;
    for (int i = 2; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    cout << dp[n] << '\n';
}

這樣做的好處就是，每一項的結果都用陣列記下來，後面要用就可以直接拿，速度快很多。

---

# DP 常見寫法

## 一維 DP

這種寫法很常見，像費波那契、爬樓梯等等，通常每一項只跟前面的幾項有關。

vector<int> dp(n+1);
// 初始值
dp[0] = ...;
// 狀態轉移
for(int i=1; i<=n; i++){
    dp[i] = ...; // 通常會用到 dp[i-1], dp[i-2] 這些前面的狀態
}

## 二維 DP

如果你發現一個狀態要用兩個參數描述（像棋盤、背包問題等），就可以這樣寫：
每個 dp[i][j] 都是靠前面的格子（例如 dp[i-1][j], dp[i][j-1]）來決定。

vector<vector<int>> dp(n+1, vector<int>(m+1));
// 初始值
dp[0][0] = ...;
// 狀態轉移
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        dp[i][j] = ...; // 這裡會用到前面格子的狀態
    }
}

---

# 小提醒

- 狀態定義很重要，建議每次寫 DP 先想清楚「這個 dp[i] 到底在存什麼
- 狀態轉移式是 DP 的靈魂，每題都要先想清楚「現在這一格怎麼用前面的格子推過來」建議可以拿紙筆出來找規律或關係
- 剛開始寫可以把 dp 陣列印出來，幫助 debug
- 有時候 DP 狀態會有很多維（像 dp[i][j][k]），不過一維、二維最常見，至少先把他們練熟(太多維的暫時也遇不到

---

# 結語

DP 一開始學的時候會很卡很正常，多練習會越來越有手感
多寫、多練，慢慢就會習慣思考「怎麼拆問題、怎麼存子問題、前面的狀態怎麼影響後面」 　

如果有人對 DP 背包有興趣可以看一下我之前編的講義
https://hackmd.io/@nowob/HyOdDegglg

---
# 例題

有時間的話會帶一下
會給大家多一點時間思考轉移式可以怎麼推
之後沒意外我會把這四題的詳解編出來，想要對答案或是搞不懂思路的同學可以之後來看看(或是直接問我

a944: 月老---骰子遊戲
b187: 雙塔事件 之壹

---