題意#
給定一個目標金額 \( x \) 以及 \( n \) 種不同面額的硬幣。
每種面額的硬幣都可以無限次使用，你的任務是計算出：總共有多少種不同的「排列方式」可以剛好湊出金額 \( x \)？
只要硬幣的使用順序不同，就算是不同的組合（例如：2+3 和 3+2 視為兩種不同的方法）。因為答案可能非常大，請將結果對 \( 10^9 + 7 \) 取餘數。
思路#
這題和「爬樓梯問題」非常相似，只不過每次能走的階數從固定的 1 或 2 步，變成了題目給定的那些硬幣面額。
我們可以定義一個陣列 dp，其中 dp[i] 代表「湊出金額 \( i \) 總共有幾種方法」。
為了要確保硬幣順序不同會被視為不同方法，我們外層的迴圈必須要是「金額（從 1 到 \( x \)）」，內層的迴圈才是「列舉每一種能用的硬幣」。
當我們在看金額 \( i \) 的時候，如果我們最後一步是用面額為 \( j \) 的硬幣來湊，那就代表在丟下這枚硬幣之前，我們的金額會是 \( i - j \)。換句話說，dp[i] 就是所有合法的 dp[i - j] 的總和。
因為題目有時間限制，一個小技巧是先把所有面額從小到大排序。這樣我們在內層迴圈列舉面額時，一旦發現某個面額 \( j \) 已經大於目標金額 \( i \) 湊不出來了，後面的面額就更不可能湊得出來，可以直接 break 提早結束，稍微省下一些運算時間。
程式碼#
#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();
int n, x, p = 1e9+7; cin >> n >> x;
// 初始化 dp 陣列，dp[0] = 1 代表湊 0 元有 1 種方法（就是什麼都不選）
vector<int> v(n), dp(x+1); dp[0] = 1;
// 讀取面額並排序，方便後續及早中斷無效迴圈
for (auto &i : v) cin >> i; sort(all(v));
// 外層列舉目標金額 i (1 ~ x)
for (int i = 1; i <= x; i++) {
// 內層列舉每一種能使用的硬幣 j
for (auto &j : v) {
if (i-j >= 0) {
// 如果這枚硬幣放得下，就把 dp[i-j] 的方法數加過來
dp[i] += dp[i-j];
// 隨時手動取模，避免加法溢位
if (dp[i] >= p) dp[i] -= p;
}
// 如果連這個比較小的面額都大於 i 了，後面的面額也一定大於 i，直接破除迴圈
else break;
}
}
cout << dp[x] << '\n';
}
