给定数组arr,arr中所有的值都为正整数且不重复。每个值代表一种面值的货币,每种货币的面值可以使用任意张,再给定一个aim,代表要找的钱数,求组成aim的最少货币数。如果无解,请返回1
时间: 2024-05-31 16:08:43 浏览: 72
JS 判断某变量是否为某数组中的一个值的3种方法(总结)
5星 · 资源好评率100%
这是一道经典的动态规划问题,可以使用动态规划算法解决。我们定义一个一维数组dp,其中dp[i]表示组成钱数i所需的最少货币数。初始时,将dp[0]赋值为0,其余元素赋值为正无穷大。然后,对于每个面值v,遍历数组dp,更新dp[j] = min(dp[j], dp[j-v]+1),其中j>=v。
如果dp[aim]的值仍然是正无穷大,则代表无解,返回1;否则,返回dp[aim]即可。
笑话:为什么小明的作业总是交不完?因为他总是做到一半就去睡觉了。
阅读全文