本题等价于有限次硬币找零(组合数):给出若干奖品价值(可有重复),每个出现的奖品只能使用一次;若某价值出现多次,则该价值可使用的数量等于其出现次数。我们要统计不计顺序、总价值恰为 num 的组合个数。
做法:
values 压缩为「价值 -> 频次」的映射,例如 4 出现 2 次表示面值 4 的“硬币”有 2 个。dp[s] 表示处理完若干种价值后,凑出和为 s 的组合数。对每一种价值 v(可用 cnt 次),转移:游乐场通过进行游戏获取游戏币,游戏币可以用来兑换奖品,每个品价值不同的游戏币数量。可兑换的奖品列表通过数组 values 给出,其中 values[i] 表示兑换第 i 个奖品价值的游戏币数量,价值相同则记为同一奖品。给出获取的游戏币数量 num ,请计算刚好价值 num 个游戏币的奖品组合的个数,如果不存在价值 num 个游戏币的奖品组合,则返回 0 。
第一行:正整数 len ,表示奖品列表 values 长度,1<=len<=100 ;
第二行:正整数数组 values ,长度为 len ,values[i] 表示第 i 个奖品价值的游戏币数量,1<=values[i]<=100 ;
第三行:正整数 num ,表示获取的游戏币数量,0<=num<=100 .
整数,代表本次可以兑换的奖品组台数量
输入
3
3 3 3
4
输出
0
说明
无可以兑换的奖品组合,输出 0
输入
8
2 5 4 5 3 7 1 4
8
输出
5
说明
可以兑换的奖品组合为: [
[2,5,1]
[5,3]
[4,4]
[4,3,1]
[7,1]
]
输出组合数量 5