题意:有10种面值为 1, 2, 5, 10, 20, 50, 100, 200, 500 ,1000
的钱 每种钱有一定的数量 给你一个总钱数,要求找出最少的钱币数量
如果找不出输出-1
思路:原以为可以用贪心解,但先付大钱,可能会无解(但其实是有解的) 用动态规划解 但你不知总钱数的范围 无法建数组
最后改用DFS深搜实现
//125MS
204K
#include <stdio.h>
int coin[] = {1,2,5,10,20,50,100,200,500,1000};
int num[11];
int ans[11],flag;
void dfs (int pay,int p)
{
if
(flag) //当前以找到 返回
return ;
if (p == -1)
......
阅读全文