提问人:Ex Nihilo 提问时间:11/2/2023 最后编辑:Ex Nihilo 更新时间:11/2/2023 访问量:102
为什么没有 Dp 的自上而下的递归函数中“硬币变化”问题没有输出?
Why does "Coin change" problem make no output in top down recursive function without Dp?
问:
自上而下的递归函数,用于查找最小硬币。
#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..)
我试图意识到这背后的主要原因。
答:
2赞
Wyck
11/2/2023
#1
不幸的是,你的算法的运行时间是指数级的,这对于计算大值的 x 是不切实际的,以一种你不会活那么久的方式。在我的计算机上,计算所需的时间大约是计算时间的 1.35 倍。bill(x+1)
bill(x)
这意味着,尽管您可以在不到一分钟的时间内完成计算,但您可能需要大约 10^31 年的时间。bill(60)
bill(100)
在实现中严重缺少记忆,在实现中,您将记住缓存中先前计算的值,而不是每次需要评估函数时完全从头开始计算它们。bill(x)
上一个:如何找到最大乘积的总和?
评论
INF
int
std::optional<int>
bill
x
std::cerr << "called bill() with x = " << x << "\n";
bill()
if(x==0)
x