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

来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum

咋啥都不会啊

2019-04-21

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

写回答

1回答

liuyubobobo

2019-04-22

已采纳

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]的方法数；

继续加油！：）

liuyubobobo

咋啥都不会啊

如果不限制数字次数，就是i：）

2019-04-23

共5条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 3