硬币找零问题变种解析：单次使用面额的DP转移公式疑问

我来帮你把这个逻辑彻底搞清楚——核心差异就在于是否允许重复使用同一枚硬币，这直接改变了动态规划状态转移的规则。我们先从状态定义入手，再对比两种情况的区别：

先明确DP状态的定义 #

首先统一伪代码里的状态含义：
dp[i][j] 表示用前j种硬币（已排序后的xs[0]到xs[j-1]）凑出金额i的总方式数。

情况1：允许重复使用硬币（原伪代码逻辑） #

当允许重复时，第11行的转移方程是：

dp[i][j] = dp[i - xs[j - 1]][j] + dp[i][j - 1]

拆解这两部分的逻辑：

• dp[i][j - 1]：不用第j种硬币的情况，直接继承用前j-1种硬币凑i的方式数。
• dp[i - xs[j - 1]][j]：使用第j种硬币的情况——因为允许重复使用，所以用了一枚xs[j-1]之后，剩下的金额i - xs[j-1]仍然可以用前j种硬币（包括第j种本身）来凑。

情况2：每种硬币仅能使用一次（修改后的逻辑） #

当限制每种硬币只能用一次时，转移方程变成：

dp[i][j] = dp[i - xs[j - 1]][j - 1] + dp[i][j - 1]

关键变化就在第一部分dp[i - xs[j - 1]][j - 1]，原因很直白：

一旦你决定使用第j种硬币，这枚硬币就不能再被使用了。因此，剩下的金额i - xs[j-1]只能用前j-1种硬币来凑——第j种已经用掉一次，无法重复调用。

我们用你给出的测试例子验证这个逻辑：

测试示例1：Change=3，面额[8,3,1,2]（排序后为[1,2,3,8]） #

计算dp[3][3]（用前3种硬币[1,2,3]凑3）时：

• 如果用了3（第3种硬币），剩下的金额是0，只能用前2种硬币凑0——方式数是dp[0][2] = 1
• 如果不用3，方式数是dp[3][2] = 1（即1+2）
• 总方式数就是1+1=2，和你给出的00122结果一致。

测试示例2：Change=4，面额[3,1,2]（排序后为[1,2,3]） #

计算dp[4][3]（用前3种硬币凑4）时：

• 如果用了3，剩下的金额是1，只能用前2种硬币凑1——方式数是dp[1][2] = 1（即1）
• 如果不用3，方式数是dp[4][2] = 3（即1+1+1+1、1+1+2、2+2）
• 总方式数就是1+3=4，和你给出的0134结果一致。

对比下来就能清晰看到：是否允许重复使用硬币，直接决定了使用当前硬币后，后续能调用的硬币范围——重复允许用前j种，不重复只能用前j-1种。

内容的提问来源于stack exchange，提问作者Abhijit Sarkar