专栏首页Zaqdt_ACMLeetCode 322. 零钱兑换(贪心+dfs剪枝)

LeetCode 322. 零钱兑换(贪心+dfs剪枝)

题目链接: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;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #507 Div.2 B. Shashlik Cooking(思维)

    题目链接:http://codeforces.com/contest/1040/problem/B

    Ch_Zaqdt
  • Codeforces Global Round 2 A. Ilya and a Colorful Walk(思维)

    版权声明:欢迎转载,若转载,请标明出处,如有错误,请指点,也欢迎大佬们给出优化方法 https://blog.csdn.net/Charles_Zaqd...

    Ch_Zaqdt
  • Codeforces Round #535 (Div. 3) C. Nice Garland(暴力)

    题目链接:http://codeforces.com/contest/1108/problem/C

    Ch_Zaqdt
  • 1007. 素数对猜想 (20)

    让我们定义 dn 为:dn = pn+1 - pn,其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相...

    AI那点小事
  • 聊聊claudb的importRDB

    claudb-1.7.1/src/main/java/com/github/tonivade/claudb/DBServerState.java

    codecraft
  • 企业云化的几个阶段!

    大多数企业都是分阶段开发和实施云战略,以便逐步适应定义的标准配置和服务政策。这个过程通常需要业务和IT部门密切合作以便定义提供的服务、服务级协议和用户自助服务能...

    用户6551894
  • 企业云化的几个阶段!

    大多数企业都是分阶段开发和实施云战略,以便逐步适应定义的标准配置和服务政策。这个过程通常需要业务和IT部门密切合作以便定义提供的服务、服务级协议和用户自助服务能...

    青果网络
  • 聊聊claudb的importRDB

    claudb-1.7.1/src/main/java/com/github/tonivade/claudb/DBServerState.java

    codecraft
  • 企业云化的几个阶段!

    大多数企业都是分阶段开发和实施云战略,以便逐步适应定义的标准配置和服务政策。这个过程通常需要业务和IT部门密切合作以便定义提供的服务、服务级协议和用户自助服务能...

    青果云小潘
  • 如何做一个高效的前端开发工程师

    不知大家有没类似这样的经历:一天忙到晚,一会被PM叫去确认需求,一会被设计拉去确认UI是否能实现,一会又被测试叫去确认bug,然后貌似做了很多事,但好像工作进度...

    用户4962466

扫码关注云+社区

领取腾讯云代金券