动态规划问题，感觉是完全背包的变种

Question

老师遇到一个问题，我有些不知道如何定义状态，和写出转移方程。
题目大意，给定15个不重复的数字。（不限制每个数字的使用次数）。给定一个数字num。
问：用这15个数字组成num的方案数是多少？

Answer 1

liuyubobobo 2019-04-22 06:33:52

dp[i][num]表示使用arr[0...i]这些元素，可以凑成num的方法数。

则：dp[i][num] = dp[i - 1][num] + dp[i - 1][num - arr[i]]

即：

使用arr[0...i]这些元素，可以凑成num的方法数等于：

1）dp[i - 1][num]：

不使用arr[i]，使用arr[0...i-1]这些元素，可以凑成num的方法数；

2）dp[i - 1][num - arr[i]]

使用arr[i]，之后使用arr[0...i-1]这些元素，可以凑成num - arr[i]的方法数；

继续加油！：）

• 提问者 咋啥都不会啊 #1

  谢谢bobo老师

• 提问者 咋啥都不会啊 #2

  dp[i - 1][num - arr[i]] 那这个num-arr[i] 下标越界，怎么处理比较好呢

• liuyubobobo 回复 提问者 咋啥都不会啊 #3

  调用前要判断是否越界啊：）请再仔细研究背包问题，背包问题有同样的越界问题，看看我们是怎么避免的？

点开查看后面2条评论