題目描述:給定不重複正整數陣列 nums 和目標 target,計算有多少種方式可以用 nums 中的數字(可重複、順序不同算不同)組合成 target。
解題思路:與爬樓梯類似,只是「步數」變為 nums 中的任意數字。定義 dp[i] 為組成總和 i 的方案數。dp[0] = 1(空組合)。對每個 i,枚舉所有 num in nums:若 num <= i,dp[i] += dp[i - num]。因為順序不同算不同,所以外層遍歷金額、內層遍歷數字(而非 0-1 背包或完全背包的不同組合排列方式)。
時間複雜度:O(target × |nums|) — 雙層迴圈。
空間複雜度:O(target) — DP 陣列大小。
1. dp[0] = 1; dp[1..target] = 0
2. For i from 1 to target:
a. For each num in nums:
- If num <= i: dp[i] += dp[i - num]
3. Return dp[target]遞迴無記憶 O(target^n) 最壞:嘗試所有組合,重複計算。
BFS O(target×n):視為圖搜尋,各金額為節點 — 邏輯不同但複雜度相同。