无DP的自顶向下递归硬币找零函数为何无输出？

问题重现 #

你提供的自顶向下递归硬币找零函数，当输入金额x大于60时会出现长时间无响应的情况，比如输入x=100预期返回1，但程序似乎陷入“无限循环”：

#define INF 1000000
int coin[5] ={100,20,10,5,1};
int bill(int x)
{
    if(x==0)
           return 0;
    if(x<0)
           return INF;
    int ans = INF;
    for(auto q:coin)
           ans =min(ans,bill(x-q)+1);
    return ans;
}

根本原因 #

不是真的无限循环，是暴力递归的重复计算导致计算量爆炸。

你的逻辑本身没问题——每个子问题最终都会到达x=0或x<0的基例，但因为没有记录已经计算过的子问题结果，同一个金额会被重复计算成千上万次：

• 比如计算bill(100)时，除了直接调用bill(0)+1（这是最优路径），还会触发bill(80)、bill(90)、bill(95)、bill(99)的计算；
• 而计算bill(80)时，又会触发bill(60)、bill(70)等，这些子问题又会继续展开更多重复计算；
• 随着x增大，子问题的数量呈指数级增长，导致程序需要消耗极长的时间才能完成计算，看起来像是卡住了。

解决办法：添加记忆化（Memoization） #

给递归函数加上记忆化，用一个数组存储已经计算过的金额对应的最小硬币数，避免重复计算：

修改后的代码 #

#define INF 1000000
int coin[5] = {100,20,10,5,1};
int memo[1001]; // 根据需求调整数组大小，这里假设最大金额不超过1000

int bill(int x)
{
    if(x == 0)
        return 0;
    if(x < 0)
        return INF;
    // 如果已经计算过该金额的结果，直接返回
    if(memo[x] != -1)
        return memo[x];
    
    int ans = INF;
    for(auto q : coin)
        ans = min(ans, bill(x - q) + 1);
    
    // 存储当前金额的计算结果，供后续调用复用
    memo[x] = ans;
    return ans;
}

使用前的初始化 #

在调用bill(x)之前，需要初始化memo数组为未计算的标记值，比如：

#include <string.h>
// ...
memset(memo, -1, sizeof(memo));

效果说明 #

添加记忆化后，时间复杂度从指数级降到O(x * n)（x是目标金额，n是硬币种类数），即使x很大（比如1000）也能瞬间得到结果。比如输入x=100时，会直接利用memo[100]的计算结果，不会再重复展开大量子问题。

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