C语言动态规划找零问题代码报错求助及解法合理性咨询

我多次尝试仍无法找出以下基于动态规划实现找零问题的C语言代码中的错误，当前输出结果不正确，希望得到帮助排查错误，同时咨询该实现方式是否为解决找零问题的理想动态规划方案。

错误代码 #

#include<stdio.h>
int min(int a , int b)
{
    if(a>b)
    {
        return b;
    }
    else if (b>a)
    {
        return a;
    }
}
void making_change(int n,int c,int value[])
{
    int i,j,m[n][c];
    for(j=1;j<=c;j++)
    {
        m[0][j]=9999;
    }
    for(i=0;i<=n;i++)
    {
        m[i][0]=0;
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= c; j++)
        {
            if (j-value[i-1]<0)
            {
                m[i][j]=m[i-1][j];
            }
            else
            {
                m[i][j]=min(m[i-1][j],1+m[i][j-value[i-1]]);
            }
        }
    }
    printf("The number of required coins are : %d",m[n][c]);
}
void main()
{
    int i,c,n;
    printf("Enter the number of different coins : ");
    scanf("%d",&n);
    int value[n];
    printf("Enter the total cost : ");
    scanf("%d",&c);
    printf("********************Enter the values of different coins******************** \n");
    for(i=0;i<n;i++)
    {
        printf("Enter the value of coin %d : ",i+1);
        scanf("%d",&value[i]);
    }
    making_change(n,c,value);
}

错误输出 #

Enter the number of different coins : 3
Enter the total cost : 8
********************Enter the values of different coins******************** 
Enter the value of coin 1 : 1
Enter the value of coin 2 : 4
Enter the value of coin 3 : 6
The number of required coins are : 0

预期正确输出 #

Enter the number of different coins : 3
Enter the total cost : 8
********************Enter the values of different coins******************** 
Enter the value of coin 1 : 1
Enter the value of coin 2 : 4
Enter the value of coin 3 : 6
The number of required coins are : 2

错误排查 #

1. 数组下标越界（核心错误）
   代码中定义的二维数组m[n][c]有效下标范围是m[0..n-1][0..c-1]，但后续循环中j取值范围是1<=j<=c、i取值范围是0<=i<=n，会导致访问m[0][c]、m[n][0]等越界位置，破坏内存中其他数据（比如初始化的m[i][0]=0被覆盖），最终输出错误的0。
   修正：将数组定义改为int m[n+1][c+1];，确保下标0..n和0..c都在有效范围内。

2. min函数未处理相等情况
   当前min函数在a==b时无返回值，会触发未定义行为（返回随机值），影响后续最小硬币数计算。
   修正：补充相等情况的返回逻辑，或简化为更健壮的实现：

   int min(int a, int b) {
       return a < b ? a : b;
   }
   

3. 初始化逻辑的有效性问题
   原代码中m[0][j]表示用0种硬币凑金额j的最小硬币数，设为9999（代表无穷大）的逻辑是正确的，但数组越界导致初始化操作破坏了其他数据，修正数组大小后该逻辑才能正常工作。

方案合理性分析 #

这个实现属于无限背包型找零问题的动态规划解法（允许重复使用同一硬币），逻辑思路是正确的：通过二维表记录前i种硬币凑j金额的最小硬币数，逐步推导最优解，但空间复杂度为O(n*c)，对于较大金额c来说不够高效。

更理想的优化方案是使用一维数组将空间复杂度压缩到O(c)，逻辑等价但空间占用更少、计算效率更高：

void making_change(int n, int c, int value[]) {
    int dp[c+1];
    // 初始化
    for (int j = 0; j <= c; j++) {
        dp[j] = 9999;
    }
    dp[0] = 0;
    // 遍历每种硬币
    for (int i = 0; i < n; i++) {
        // 遍历金额，从小到大（允许重复选当前硬币）
        for (int j = value[i]; j <= c; j++) {
            dp[j] = min(dp[j], dp[j - value[i]] + 1);
        }
    }
    printf("The number of required coins are : %d", dp[c]);
}

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