alan23273850 的刷題筆記
d280: 骰子問題
Tags: dp
出處：https://zerojudge.tw/ShowProblem?problemid=d280
提交：https://zerojudge.tw/Submissions?problemid=d280&account=allllllan123456
問題：給定 $N\in[1,20]$ 個骰子，請問這些骰子能一同擲出總和為 $M\in[N,6N]$ 點的方法數有多少。
解法：就經典的 DP，把問題拆成最後一個骰子與前面所有骰子兩組來看，如果我最後一個骰子只擲出 1 點，那前面所有骰子就必須擲出 M-1 點；如果我最後一個骰子只擲出 2 點，那前面所有骰子就必須擲出 M-2 點，依此類推，所以就根據最後一個骰子的點數進行方法數的討論與加總即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4long long DP[21][121];
5
6long long f(int n, int m) {
7 if (m<n || m>6*n) return 0;
8 if (n == 1) return 1;
9 if (DP[n][m]) return DP[n][m];
10 return DP[n][m] = f(n-1, m-1) + f(n-1, m-2) + f(n-1, m-3)
11 + f(n-1, m-4) + f(n-1, m-5) + f(n-1, m-6);
12}
13
14int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
15 int T; cin >> T;
16 while (T--) {
17 int a, b; cin >> a >> b;
18 cout << f(a,b) << '\n';
19 }
20 return 0;
21}