题目链接:https://leetcode-cn.com/problems/coin-change/
这道题刚开始用bfs去写的,应该是没有剪枝吧,然后超时了,感觉加个剪枝应该也没啥问题。后来改写dfs,这道题要求使用的硬币数量尽量少,那么这里就需要贪心的去优先使用面值大的硬币,所以先sort一下,然后去dfs搜索,对于第p枚硬币,因为面值从大到小所以要尽量多的去买,所以这里也是一个贪心。还有就是要进行两次剪枝,第一次是当已经达到了target面值的时候就不用再往下搜了,第二次是当硬币数已经大于ans了,也就没必要再搜下去了。描述的不是很清楚,但是代码还是比较好懂的,直接看代码会更好一点。
AC代码:
class Solution {
public:
int ans;
void dfs(vector<int>& c, int p, int target, int num){
if(p < 0) return ;
for(int i=target/c[p];i>=0;i--){ // 尽量多的去使用当前硬币
int tmp = target - i * c[p]; // 使用了i个c[p]硬币后的值
int cnt = num + i;
if(tmp == 0){ // 达到目标后直接break
ans = min(ans, cnt);
break;
}
if(cnt + 1 >= ans) break; // 没必要再往下搜了
dfs(c, p - 1, tmp, cnt);
}
}
int coinChange(vector<int>& c, int amount) {
sort(c.begin(), c.end());
ans = 0x3f3f3f3f;
dfs(c, c.size() - 1, amount, 0);
return ans == 0x3f3f3f3f ? -1 : ans;
}
};