解题思路
本题等价于有限次硬币找零（组合数）：给出若干奖品价值（可有重复），每个出现的奖品只能使用一次；若某价值出现多次，则该价值可使用的数量等于其出现次数。我们要统计不计顺序、总价值恰为 num 的组合个数。
做法：
- 先将
values 压缩为「价值 -> 频次」的映射，例如 4 出现 2 次表示面值 4 的“硬币”有 2 个。
- 使用二维计数 DP（组合型）：
设
dp[s] 表示处理完若干种价值后，凑出和为 s 的组合数。对每一种价值 v（可用 cnt 次），转移：
P4234.第1题-奖品兑换组合
题目内容
游乐场通过进行游戏获取游戏币，游戏币可以用来兑换奖品，每个奖品价值不同的游戏币数量。可兑换的奖品列表通过数组 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 .
输出描述
整数，代表本次可以兑换的奖品组台数量
样例1
输入
3
3 3 3
4
输出
0
说明
无可以兑换的奖品组合，输出 0
样例2
输入
8
2 5 4 5 3 7 1 4
8
输出
5
说明
可以兑换的奖品组合为:
[
[2,5,1]
[5,3]
[4,4]
[4,3,1]
[7,1]
]
输出组合数量 5
