硬币找零问题：动态规划矩阵解法逻辑错误排查求助

我帮你找到了代码里的关键逻辑错误，导致计算结果不符合预期：

核心错误点 #

1. 错误的dp[0][j]初始化循环范围 #

原代码中初始化第一行（用0种硬币凑金额j）的循环写反了范围：

for(int j=1;j<n;j++) {
    dp[0][j]=0;
}

这里循环上限是n（硬币的数量），但我们需要初始化的是金额从1到sum的所有情况。当sum大于n时，大部分dp[0][j]的值还是memset设置的-1，后续动态规划计算会使用这些错误值，最终导致结果完全错误。

2. memset初始化的潜在风险 #

memset(dp,-1,sizeof(dp))会把每个int字节都设为0xff，也就是整数值-1，但后续的初始化没有覆盖所有需要的位置。比如当sum很大时，未被循环处理的dp[0][j]仍为-1，会干扰计算逻辑。

修正后的代码 #

我调整了初始化逻辑，同时改用vector避免栈溢出问题（当sum较大时，栈上的二维数组容易触发溢出）：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#define ll long long
//Author: Nilargha Roy (neel13)
using namespace std;

int coinchangeways(int arr[],int n,int sum) {
    // 用vector创建dp数组，默认初始化所有元素为0，避免栈溢出
    vector<vector<int>> dp(n+1, vector<int>(sum+1, 0));
    
    // 初始化：用任意数量的硬币凑0元，只有1种方式（不用硬币）
    for(int i=0;i<=n;i++) {
        dp[i][0] = 1;
    }
    
    // 动态规划核心计算
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=sum;j++) {
            if(arr[i-1] <= j)
                // 选当前硬币 + 不选当前硬币的组合数之和
                dp[i][j] = dp[i][j-arr[i-1]] + dp[i-1][j];
            else
                // 只能不选当前硬币
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][sum];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef __APPLE__
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    int n;
    cin>>n;
    // 改用vector存储硬币面额，符合C++标准（避免非标准变长数组）
    vector<int> arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int sum;
    cin>>sum;
    cout<<coinchangeways(arr.data(),n,sum);
}

修正说明 #

1. 数组初始化优化：用vector创建dp数组，默认值为0，省去了memset和错误的循环初始化步骤，同时避免栈溢出风险。
2. 正确的边界条件：第一列dp[i][0] = 1，表示凑0元的方式只有1种（不用任何硬币）；第一行dp[0][j] = 0，表示用0种硬币凑任何正金额都没有方式，符合逻辑。
3. 标准兼容改进：main函数中改用vector<int>存储硬币面额，避免使用非标准的变长数组int arr[n]。

测试你提到的例子：输入{1,2,3}、SUM=5，修正后的代码会输出正确的5，对应组合为：

• 1+1+1+1+1
• 1+1+1+2
• 1+2+2
• 1+1+3
• 2+3

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