硬币找零DP解法中将目标和sum作为列大小的实现是否正确？

在求解硬币找零计数问题（统计使用给定硬币集合凑出目标和的方案总数，每种硬币可重复使用）时，动态规划制表法的常见实现是将硬币数组长度设为DP表列数、目标和sum设为DP表行数。我此前看到说法称，采用反向维度设计——即列数等于目标和sum、行数等于硬币数组长度的写法无法得到正确结果。但我自行编写对应代码测试后得到了符合预期的正确答案，想确认是此前的说法存在错误，还是我的代码实现有隐藏问题。

实现代码 #

void coinChange_3(vector<int> arr, int sum) {
    int n=arr.size();
    vector<vector<int>> dp(n+1, vector<int>(sum+1));
    for(int i=0; i<=n; i++) dp[i][0]=1;
    for(int i=1; i<=sum; i++) dp[0][i]=0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=sum; j++) {
            dp[i][j]=dp[i-1][j];
            if(j>=arr[i-1]) dp[i][j]+=dp[i][j-arr[i-1]];
        }
    }
    for(int i=0; i<=n; i++) {
        for(int j=0; j<=sum; j++) {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
}

测试调用与运行结果 #

调用代码：

coinChange_3({1, 2, 3}, 4);

运行输出：

1 0 0 0 0 
1 1 1 1 1 
1 1 2 2 3 
1 1 2 3 4

解答 #

此前的说法存在错误，DP表的行列维度本质只是索引映射的选择，只要状态定义、转移逻辑和维度设计匹配，调换行列完全不会影响结果正确性，你的代码实现没有逻辑问题。
具体验证如下：

• 状态定义清晰准确：你的代码中dp[i][j]表示使用前i种硬币凑出面值j的总方案数，完全对应无界硬币找零（每种硬币可重复选取）的计数场景。
• 边界条件设置正确：
  • 凑出0面值的方案数恒为1（不选取任何硬币），因此所有dp[i][0] = 1
  • 不使用任何硬币时，无法凑出大于0的面值，因此所有dp[0][i] = 0
• 状态转移逻辑完全符合要求：
  • 不使用第i种硬币的场景：方案数直接继承前i-1种硬币凑j的结果，即dp[i-1][j]
  • 使用至少1枚第i种硬币的场景：等价于先拿1枚第i种硬币，再用前i种硬币凑剩余的j - arr[i-1]面值，对应无界背包允许重复选物品的特性，因此加上dp[i][j-arr[i-1]]
• 测试结果校验正确：用硬币{1,2,3}凑4的合法方案共4种，分别是1*4、1*2+2、2*2、1+3，和你代码输出的最终结果dp[3][4] = 4完全一致。

之前所谓「反向维度无法得到正确结果」的说法，本质是混淆了「维度调换」和「逻辑写错」：很多人调换维度时会顺带着写错转移依赖，比如把无界背包的转移写成取上一行的dp[i-1][j-arr[i-1]]（变成0-1背包逻辑），或者搞反循环顺序导致重复/遗漏计数，才会得到错误结果，和维度本身的行列选择没有关系。

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