为什么“硬币找零”问题在没有 Dp 的情况下自上而下的递归函数没有输出？

Question

自顶向下递归函数找到最小硬币。

#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 的值大于 50 时，我在输出中没有发现任何类似程序进入无限循环的内容。这背后的真正原因是什么？我在这里看不到循环，因为每个子问题总是会达到基本情况。

input: x=100
expected output : 1

0utput: (not terminated ... ... loading..)

我试图了解这背后的主要原因。

Answer 1

不幸的是，你的算法的运行时间是指数级的，以“你不会活那么久”的方式计算大的 x 值是不切实际的。在我的计算机上，计算

bill(x+1) 所需的时间大约是计算 bill(x) 的 1.35 倍。

这意味着，虽然您可以在不到一分钟的时间内计算出 

bill(60)

，但您可能预计 

bill(100)

需要大约 10^31 年

。

您在实现中严重缺少

记忆

，您会在缓存中记住之前计算的

bill(x)值，而不是每次需要评估函数时完全从头开始计算它们。