題意#
這題是前面換零錢問題的變化型。同樣給定金額上限 \( x \) 及 \( n \) 種硬幣面額，每種無限次使用。
但這次的重點是：不考慮順序的所有「組合」。也就是說，2+3 跟 3+2 會被視為同一種方法，我們只想知道有幾種挑選硬幣的組合可以剛好湊出 \( x \) 元。
最後的組合數依然可能很大，需要對 \( 10^9 + 7 \) 取模。
思路#
要解決「不考慮排列順序的組合數」問題，最關鍵的是我們寫雙層迴圈的順序。
在上一個版本（Coin Combinations I，計算排列數）中，我們是外層迴圈跑金額、內層迴圈跑面額。這等同於在每一步都允許放入任何一種硬幣，所以會產生不同的排列順序。
為了避免重複計算不同順序的排列，我們必須把順序反過來：外層迴圈跑硬幣面額，內層迴圈跑目標金額。
這樣做的意義是：「我們先只用第一種硬幣來看能湊出多少金額，接著開放第二種硬幣，再來開放第三種……」。透過這樣逐一引入新硬幣的方式，我們強迫自己每次都是「先把這面額用完，再去考慮下一個面額」，自然就不會出現先拿 A 再拿 B，跟先拿 B 再拿 A 被重複計算兩次的問題，完美達成了「無序組合」的要求。
程式碼#
#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 元有一種組合方法
vector<int> v(n), dp(1000001); dp[0] = 1;
// 讀取各種硬幣的面額
for (auto &i : v) cin >> i;
// 關鍵所在：外層迴圈先固定「只能用哪種硬幣」
for (auto &j : v) {
// 內層迴圈再列舉「要湊出的目標金額」
// 正序遍歷，因為每種硬幣可以無限拿取
for (int i = j; i <= x; i++) {
// 這個金額的組合數，加上「扣掉當前這枚硬幣面額」的組合數
dp[i] += dp[i-j];
// 避免溢位，隨時取模
if (dp[i] >= p) dp[i] -= p;
}
}
cout << dp[x] << '\n';
}
