求助！用递归实现硬币凑整(c 语言，复试上机题)

计算机程序的构造与解释那本书有讲

if f(x,y,z) > 100: return []
if f(x,y,z) == 100: return [(x,y,z)]
if f(x,y,z) == 99: return [(x+1, y, z)]
if f(x,y,z) == 98: return [(x, y+1, z), (x+2, y, z)]
if f(x,y,z) == 95: return [(x+5,y,z), (x+3,y+1,z), ...]

return [flat(f(x+1, y, z)), flat(f(x, y+1, z)), flat(f(x, y, z+1))]

具体说就是 1 元钱用 5 分与不用 5 分用剩下的钱币类型来计算，函数第一次运行后条件变为 9 角 5 分有多少种方法凑成和 1 元钱用 1 分，2 分有多少种方法凑成，通过递归调用将条件慢慢收敛

递归问题基本都是树结构的，画个图就出来了

```
package main
import (
"fmt"
)
func solve(money, x, y, z, last int) int{
if money == 0 {
return 1
}
count := 0
if money >= 1{
count = count + solve(money - 1, x + 1, y, z, 1)
}
if money >= 2 && last >= 2{
count = count + solve(money - 2, x, y + 1, z, 2)
}
if money >= 5 && last == 5{
count = count + solve(money - 5, x, y, z + 1, 5)
}
return count
}
func main(){
fmt.Println(solve(100, 0, 0, 0, 5))
}
```

Golang 版

现在的人写代码连个 dfs 都不会了么?

迭代还是递归

这 tm 不就是线性 dp 吗？

用得着 dfs，递归啥的吗……

这应该用 dp 吧，当然记忆化递归搜索也可以

@webjin1
@aheadlead
@victor97
题目要求使用递归，我也知道这个有更优解。。

PHPer .... 闲得无聊写了一下

$count = 0;

function coinCombination($target)
{
if ($target == 0) {
global $count;
$count++;
} elseif ($target < 0) {
return;
}

coinCombination($target - 1);
coinCombination($target - 2);
coinCombination($target - 5);
}

coinCombination(5);
echo $count;

@carlclone target 传 100...

糟糕错了, 得用记忆化搜索 , 在 V2 发言一不小心就暴露智商