为什么没有 Dp 的自上而下的递归函数中“硬币变化”问题没有输出?

Why does "Coin change" problem make no output in top down recursive function without Dp?

提问人:Ex Nihilo 提问时间:11/2/2023 最后编辑:Ex Nihilo 更新时间:11/2/2023 访问量:102

问:

自上而下的递归函数,用于查找最小硬币。

#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 的值大于 60 时,我在输出中没有发现任何内容,例如程序进入无限循环。这背后的真实含义是什么?我在这里没有看到没有循环,因为每个子问题总是会到达基本情况。

input: x=100
expected output : 1

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

我试图意识到这背后的主要原因。

C++ 算法 递归 动态规划

评论

0赞 user17732522 11/2/2023
不幸的是,我完全不明白你想问什么。显示的代码中没有输出。此外,它没有定义(它不是标准的),并且不能保存无穷大的值。请展示一个完整的最小可重复示例,包括您得到的输出和您期望的输出,然后解释您对哪些感到困惑。INFint
0赞 Pepijn Kramer 11/2/2023
旁注:不建议返回“特殊”返回值。如果无法满足前/后条件,则抛出异常或返回(或C++23的 [std::expected])en.cppreference.com/w/cpp/utility/expected))。std::optional<int>
2赞 user17732522 11/2/2023
没有无限循环。您只是没有给程序足够的时间来完成。考虑调用次数(以及程序运行时)将如何随着算法的增加而增加。此外,请考虑递归的深度,并检查它是否不会超过堆栈大小。最好使用迭代方法而不是递归方法,以避免超过堆栈限制。billx
0赞 JaMiT 11/2/2023
“我看不出这里没有周期,因为”——因为你是从理论上看的?切换到实际的观点相当简单。只需添加一些输出来跟踪函数调用,例如在开头(就在之前)。有周期吗?周期中的价值是什么?std::cerr << "called bill() with x = " << x << "\n";bill()if(x==0)x
0赞 Asesh 11/2/2023
使用记忆,否则完成程序将过于昂贵和耗时,也可能导致堆栈溢出。Neetcode 使用记忆解决了这个程序

答:

2赞 Wyck 11/2/2023 #1

不幸的是,你的算法的运行时间是指数级的,这对于计算大值的 x 是不切实际的,以一种你不会活那么久的方式。在我的计算机上,计算所需的时间大约是计算时间的 1.35 倍。bill(x+1)bill(x)

这意味着,尽管您可以在不到一分钟的时间内完成计算,但您可能需要大约 10^31 年的时间。bill(60)bill(100)

在实现中严重缺少记忆,在实现中您将记住缓存中先前计算的值,而不是每次需要评估函数时完全从头开始计算它们。bill(x)