K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知有面额为coins = [1,2,5]的硬币无数枚，需要凑出总金额amount=11，求所需的最少硬币数量。
coins = [1,2,5]
amount=11
状态转移方程应为dp[j] = max(dp[j], dp[j - coin] + 1)，数组初始值全设为0
dp[j] = max(dp[j], dp[j - coin] + 1)
为避免硬币重复选取，内层遍历背包容量需采用从大到小的逆序遍历
该问题的最优解需要4枚硬币，组合为2+2+2+5
该问题属于完全背包的最值类变种，初始化时dp[0] = 0，其余位置需初始化为大于amount的极大值避免初始值干扰结果
dp[0] = 0