題意#
這是一題很基礎的動態規劃入門題。
你有一顆標準的六面骰子（可以擲出 1 到 6 的點數），問題是要計算出：總共有多少種不同的擲骰子組合，它們加起來的點數總和剛好等於 \( n \)？
因為組合數量可能會非常大，所以最後的答案需要對 \( 10^9 + 7 \) 取餘數。
思路#
這題的核心概念其實跟爬樓梯問題（每次可以走一階或兩階）很像，只是我們現在每次可以走的階數變成了 1 到 6 階。
我們可以定義一個陣列 v，其中 v[i] 代表「要湊出總和為 \( i \) 點的所有可能組合數量」。
要湊出總點數 \( i \)，我們最後一次擲骰子可能擲出的是 1 到 6 之中的任何一個點數（假設為 \( k \)）。那麼在最後一次擲出 \( k \) 之前，我們前面的點數總和必須剛好是 \( i - k \)。
所以，我們要求的狀態轉移方程就很清楚了：v[i] 等於 v[i-1] + v[i-2] + ... + v[i-6]，也就是把前面六個點數的組合數量全部加總起來就是答案。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
// 陣列大小開到題目 n 的上限 10^6
vector<int> v(1000001);
int p = 1e9+7;
// 初始化：直接擲出 1~6 點的方法各有 1 種
for (int i = 1; i <= 6; i++) v[i] = 1;
int n; cin >> n;
// 從點數 2 開始由小到大計算到 n
for (int i = 2; i <= n; i++) {
// 枚舉最後一次擲骰子可能的點數（對應前一個狀態 j）
for (int j = i-6; j < i; j++) {
// j > 0 代表前一個狀態是合法的
// 把前面 6 個狀態的次數加總，並隨時取模
if (j > 0) v[i] = (v[i] + v[j]) % p;
}
}
cout << v[n] << '\n';
}
