322. Coin Change

最新推荐文章于 2024-03-19 21:22:22 发布

coding_ironboy

最新推荐文章于 2024-03-19 21:22:22 发布

阅读量78

点赞数

本文链接：https://blog.csdn.net/coding_ironboy/article/details/101228009

版权

本文介绍了一个解决硬币找零问题的动态规划算法，通过一个名为coinChange的函数实现，该函数接收硬币面额数组和目标金额作为参数，返回所需的最少硬币数量。若无法找零，则返回-1。文章附带了YouTube视频教程链接，详细讲解了算法原理和实现过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

   int coinChange(vector<int> &coins, int amount) {
        vector<int> ans(amount + 1, amount+10);
        ans[0] = 0;
        for (int i = 1; i < amount+1; i++) {
            for (int j = 0; j < coins.size(); j++)
                if (i >= coins[j])
                    ans[i] = min(ans[i], ans[i - coins[j]] + 1);
        }
        if(ans.back()<amount+1) return ans.back();
        else return -1;
    }

dp：bottom-up做法

youtube：https://www.youtube.com/watch?v=jgiZlGzXMBw&t=502s