换零钱

[编程题]换零钱

有一个数组changes，changes中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，对于一个给定值x，请设计一个高效算法，计算组成这个值的方案数。

给定一个int数组changes，代表所有零钱，同时给定它的大小n，另外给定一个正整数x，请返回组成x的方案数，保证n小于等于100且x小于等于10000。

测试样例：

[5,10,25,1],4,15

返回：6

测试样例：

[5,10,25,1],4,0

返回：1

算法知识视频讲解

重生之我要当分子

发表于 2024-12-31 23:44:41

解题思路这是一个完全背包问题的变种，求组合数。关键点：状态定义：表示组成金额的方案数状态转移：对每个面值，更新所有可能的金额边界条件：，表示金额为时有种方案（什么都不选）金额为负数时方案数为代码 cpp java py 展开全文

问题信息

动态规划

来自：面试常考算法题(八)-...

难度：

37条回答 95收藏 20040浏览

查看代码

换零钱

扫一扫，把题目装进口袋