这题挺有意思的,来源是 SPOJ-TSUM,题意大概是,给出 个物品,第
个物品的价值为
,问在这
个物品中选出
个或
个或
个价值和是多少,对于每个价值求出方案个数,在这题中
和
算作一种方案
例如有三个物品
![]() |
![]() |
![]() |
1 | 2 | 3 |
选一个就可以得到 三种价值
选两个就可以得到 三种价值
选三个就可以得到 一种价值
所以最后答案就是
价值 | 1 | 2 | 3 | 4 | 5 | 6 |
方案数 | 1 | 1 | 2 | 1 | 1 | 1 |