“动态规划”的本质就是“记忆化递归”，有很多重复子问题，所以必须“记忆”。
例 1 ：LeetCode 第 416 题：分割等和子集
传送门：分割等和子集。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].示例 2:
输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
分析：如果在前面的几个整数中，可以找到全部整数和一半的整数，这个问题就得到了解决。这是一个典型的 背包问题，即：要求我们在
个物品中选出一定物品，填满容量为
的背包。
于是我们可以使用“动态规划”来解决，“动态规划”在本质上是“记忆化递归”。关键在于定义“状态”，递推得到“状态转移方程”。
第 1 步：定义“状态”。
：考虑“编号”从
到
这
个物品是否能够填满容量为
的背包。
第 2 步：找到“状态转移方程”。
分类讨论：分“要当前这个数”和“不要当前这个数”两个情况考虑，则“状态转移方程”为： =
or 。
时间复杂度：。所有数字和为
，背包最大为
，
（
万）。
写法1：“记忆化递归”，这个写法会超时，应该改用从下到上的动态规划来做，不过理解下面这种写法有助于我们理解“动态规划”的本质。
Python 代码：
class Solution:
def __init__(self):
self.cache = None
def __try_partition(self, nums, index, C):
"""
给定 nums 表示给出的容量，考虑索引区间 [0, index] ，是否能够得到 sum_
分类讨论的标准就是要不要 nums[index] 这个物品
f(i,j) = f(i-1,j) or f(i,j-nums[i])
:param nums:
:param index:
:param C:
:return:
"""
# 先写递归终止条件
if C == 0:
return True
if index < 0 or C < 0:
return False
if self.cache[index][C]:
return self.cache[index][C]
# 情况1：不考虑 nums[index] 这个物品，看看能不能满足条件
res = self.__try_partition(nums, index - 1, C)
# 情况2：考虑 nums[index] 这个物品，如果它可以放进背包
if nums[index] <= C:
res = res or self.__try_partition(nums, index - 1, C - nums[index])
self.cache[index][C] = res
return res
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
l = len(nums)
if l == 0:
return False
# 特判：如果价值为奇数，不可以，直接返回 False
s = sum(nums)
if s & 1 == 1:
return False
half = s // 2
self.cache = [[None for _ in range(half + 1)] for _ in range(l)]
return self.__try_partition(nums, l - 1, half)
写法2：动态规划。
Python 代码：
class Solution:
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# 物品的数量
l = len(nums)
if l == 0:
return False
s = sum(nums)
if s & 1 == 1:
return False
# 二维 dp 问题：背包的容量
half = s // 2
dp = [[0 for _ in range(half + 1)] for _ in range(l)]
# 其实使用一维数组就可以了
# 先写第 1 行：看看第 1 个数是不是能够填满这个背包
for i in range(half + 1):
dp[0][i] = False if nums[0] != i else True
# i 表示物品索引
for i in range(1, l):
# j 表示容量
for j in range(half + 1):
if j >= nums[i]:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
练习 1 ：LeetCode 第 322 题：Coin Change
传送门：322. 零钱兑换。
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
-1。示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1示例 2:
输入: coins = [2], amount = 3 输出: -1说明:
你可以认为每种硬币的数量是无限的。
思路：使用动态规划。
第 1 步：定义状态。
dp[i]：凑齐总价值 i 需要的最少硬币数，状态就是问的问题。
第 2步：思考“状态转移方程”。
假设dp[11] = 3，如何递推得到“状态转移方程”呢？
dp[12] = min（ dp[11] + （1 这一枚硬币）,
`dp[10]` +（ 2 这一枚硬币）,
`dp[7]` + （5 这一枚硬币）)。
这里要注意的一点是：1、首先硬币的面值应该要小于等于当前要凑出来的面值；2、剩余的那个面值应该不是 ，满足以上两点，才是“状态转移方程”。
这样就把一个大问题向一个小问题转化。要注意的地方：求最小值，因此我们的初始值应该设置成一个很大的值去和计算出来的值比较，取其中较小的那一个。这里题目中给出了 的定义，因此我们在编码的时候，应该要考虑什么时候我们定义的状态的值为
，即已经有的硬币的都不能凑出指定金额的时候。
Java 代码：
public class Solution {
public int coinChange(int[] coins, int amount) {
int len = coins.length;
if (amount == 0) {
return 0;
}
if (coins == null || len == 0) {
return -1;
}
// 要把 0 算进去，这是基本情况，所以开辟 coins 这么多空间的
// 组成当前的总价值需要的最少硬币数
int[] dp = new int[amount + 1];
// dp 问题的套路，把初值先算出来，因为递归到底的时候，可能到这个地方
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
int minCount = Integer.MAX_VALUE;
for (int j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0 && dp[i - coins[j]] != -1) {
minCount = Integer.min(dp[i - coins[j]] + 1, minCount);
}
}
dp[i] = minCount == Integer.MAX_VALUE ? -1 : minCount;
}
return dp[amount];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] coins = {1};
int amount = 0;
int coinChange = solution.coinChange(coins, amount);
System.out.println(coinChange);
}
}
Python 代码：
class Solution:
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
# 特判
size = len(coins)
if size == 0:
return -1
dp = [0 for _ in range(amount + 1)]
for i in range(1, amount + 1):
min_val = 9999
for j in range(0, size):
# 注意：能分割，并且有值才进行比较
if i - coins[j] >= 0 and dp[i - coins[j]] != -1:
min_val = min(min_val, dp[i - coins[j]] + 1)
if min_val == 9999:
dp[i] = -1
else:
dp[i] = min_val
return dp[-1]
if __name__ == '__main__':
coins = [1, 2, 5]
amount = 11
solution = Solution()
result = solution.coinChange(coins, amount)
print(result)
优化思路：dp[x + c] = min(dp[x] + 1, dp[x + c])。
Python 代码：
class Solution:
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [0] + [-1] * amount
for x in range(amount + 1):
if dp[x] == -1:
continue
for c in coins:
if x + c > amount:
continue
if dp[x + c] == -1 or dp[x + c] > dp[x] + 1:
dp[x + c] = dp[x] + 1
return dp[-1]
if __name__ == '__main__':
coins = [1, 2, 5]
amount = 11
solution = Solution()
result = solution.coinChange(coins, amount)
print(result)
参考资料：https://blog.csdn.net/asd136912/article/details/79080693
总结：这道题其实不难，但是在实现上有一些小的细节要处理。
练习 2 ：LeetCode 第 377 题 ：Combination Sum IV
传送门：377. 组合总和 Ⅳ。
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3] target = 4 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。 因此输出为 7。进阶：
如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？致谢：
特别感谢 @pbrother 添加此问题并创建所有测试用例。
思路：定义状态 dp[i]：和为 i 的正整数的组合个数。
要特别注意：在 这一点，我们是定义
dp[0] = 1的，因为它表示如果 nums 里有一个数恰好等于 target，它单独成为 1 种可能。
Python 代码：
class Solution:
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
size = len(nums)
if size == 0 or target <= 0:
return 0
dp = [0 for _ in range(target + 1)]
# 这一步很关键，想想为什么 dp[0] 是 1
# 因为 0 表示空集，空集和它"前面"的元素凑成一种解法，所以是 1
# 这一步要加深体会
dp[0] = 1
for i in range(1, target + 1):
for j in range(size):
if i >= nums[j]:
dp[i] += dp[i - nums[j]]
return dp[-1]
Java 代码：与上面的写法等价
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i < target + 1; i++) {
for (int num : nums) {
if (i >= num) {
dp[i] = dp[i] + dp[i - num];
}
}
}
return dp[target];
}
}
下面这种写法从下往上更新。
Java 代码：
public int combinationSum4(int[] nums, int target) {
int[] memo = new int[target + 1];
memo[0] = 1;
for (int i = 0; i < target; i++) {
for (int num : nums) {
if (i + num <= target) {
memo[i + num] += memo[i];
}
}
}
return memo[target];
}
练习 3 ：LeetCode 第 474 题：Ones and Zeroes
传送门：474. 一和零。
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个
0和 n 个1。另外，还有一个仅包含0和1字符串的数组。你的任务是使用给定的 m 个
0和 n 个1，找到能拼出存在于数组中的字符串的最大数量。每个0和1至多被使用一次。注意:
- 给定
0和1的数量都不会超过100。- 给定字符串数组的长度不会超过
600。示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3 输出: 4 解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1 输出: 2 解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
注意：什么叫组成？必须用完？还是有剩余就可以？
练习 4 ：LeetCode 第 139 题： Word Break
传送门：139. 单词拆分。
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
思路：动态规划。
状态：dp[i] 表示 s[0:i] 可以被空格拆分，拆分以后的单词全落在 wordDict 中。这个状态就是题目要求的。
状态转移方程；dp[j] = dp[i] and s[i + 1,j] in wordDict。注意：编写代码上有技巧，一定是先判断 s[i + 1,j] in wordDict，这样可以很快得出前缀字符串是否可以分割。
写法1：记忆化递归，自上而下。
Python 代码：注意：先看右边在不在单词字典中，注编码的细节，不考虑空字符串，所以 j 从 1 开始，到 ·size -1 结束
class Solution:
def __init__(self):
self.memo_ = dict()
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
# 题目说了 s 非空，wordDict 非空
word_set = set(wordDict)
return self.__word_break(s, word_set)
def __word_break(self, s, word_set):
# 首先看缓存
if s in self.memo_:
return self.memo_[s]
# 特判
if s in word_set:
self.memo_[s] = True
return True
res = False
for j in range(1, len(s)):
left = s[:j]
right = s[j:len(s)]
# 注意：不要把 self.__word_break(left, word_set) 这一个判断放在前面
# 否则会发生死循环，如果在代码编写过程中出现死循环，不要着急，debug 一下
# 很快就会找到原因的
if right in word_set and self.__word_break(left, word_set):
res = True
break
self.memo_[s] = res
return res
写法2：动态规划，自下而上。
注意1：需要长度为 的状态，定义为
True，因为要处理一种特例，即整个字符串恰好就在 wordDict 中；
注意2：注意边界条件：后数组的起始索引，表示了前数组的长度。
Python 代码：重点关注这里设置 dp[0] = True 的原因
class Solution:
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
size = len(s)
word_set = set(wordDict)
# dp[i]：长度为 i 的 s 字符串经过空格分隔以后在 wordDict 中
# 需要长度为 0，因此前面加上一个 True
dp = [True] + [False for _ in range(size)]
for i in range(1, size + 1):
# j 其实就是前缀的长度，注意这个细节
for j in range(i):
right = s[j:i]
if right in word_set and dp[j]:
dp[i] = True
# 注意，这里 break
break
return dp[-1]
if __name__ == '__main__':
s = "leetcode"
wordDict = ["leet", "code"]
solution = Solution()
result = solution.wordBreak(s, wordDict)
print(result)
LeetCode 第 140 题：单词拆分 II
传送门：140. 单词拆分 II。
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
- 分隔时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] 输出: [ "cats and dog", "cat sand dog" ]示例 2：
输入: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] 输出: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] 解释: 注意你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: []
思路：先用第 139 题做预处理，然后再 DFS，DFS 的时候，后面分割出来的单词先加入。
Python 代码：关键在于使用 dp 数组作为 DFS 的判断条件。
class Solution:
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
size = len(s)
if size == 0:
return None
word_set = set(wordDict)
# dp[i] 表示长度为 i 的 s，满足题意
# 0 表示 False ，1 表示 True
dp = [0 for _ in range(size + 1)]
dp[0] = 1
for i in range(1, size + 1):
# i 表示 s 子串的长度
for j in range(i):
# j 表示后子串的起始位置，最多到 i-1
# j 也正正好表示前子串的长度
if s[j:i] in word_set and dp[j]:
dp[i] = 1
res = []
if dp[-1]:
self.__dfs(s, size, wordDict, res, [], dp)
return res
def __dfs(self, s, length, wordDict, res, path, dp):
if length == 0:
res.append(' '.join(reversed(path)))
return
for i in range(length):
cur = s[i:length]
if dp[i] and cur in wordDict:
path.append(cur)
self.__dfs(s, i, wordDict, res, path, dp)
path.pop()
练习5：LeetCode 第 494 题：Target Sum
传送门：494. 目标和。
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号
+和-。对于数组中的任意一个整数，你都可以从+或-中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3 输出: 5 解释: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 一共有5种方法让最终目标和为3。注意:
- 数组的长度不会超过20，并且数组中的值全为正数。
- 初始的数组的和不会超过1000。
- 保证返回的最终结果为32位整数。
思路1：搜索，回溯。
Python 代码：提交到 LeetCode 上会超时
class Solution:
def __init__(self):
self.res = 0
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
size = len(nums)
self.__dfs(nums, size, 0, 0, S)
return self.res
def __dfs(self, nums, size, start, cur_sum, S):
if start == size:
# 到尾巴了，看看累积和是不是达到 S 了
if cur_sum == S:
self.res += 1
return
else:
self.__dfs(nums, size, start + 1, cur_sum + nums[start], S)
self.__dfs(nums, size, start + 1, cur_sum - nums[start], S)
if __name__ == '__main__':
solution = Solution()
nums = [35, 25, 24, 23, 2, 47, 39, 22, 3, 7, 11, 26, 6, 30, 5, 34, 10, 43, 41, 28]
S = 49
result = solution.findTargetSumWays(nums, S)
print(result)
C++ 代码：
class Solution {
int res=0;
int sum=0;
int len=0;
public:
int findTargetSumWays(vector<int>& nums, int S) {
len=nums.size();
dfs(nums,0,S);
return res;
}
void dfs(vector<int>& nums,int p,int s){
if(p==len){
if(s==sum)++res;
return;
}
sum+=nums[p];
dfs(nums,p+1,s);
sum-=2*nums[p];
dfs(nums,p+1,s);
sum+=nums[p];
}
};
Java 代码：
class Solution {
public int findTargetSumWays(int[] nums, int S) {
return findTargetSumWays(nums, 0, S, 0);
}
private int findTargetSumWays(int[] nums, int index, int S, int sum) {
int res = 0;
if (index == nums.length) {
return sum == S ? ++res : res;
}
res += findTargetSumWays(nums, index + 1, S, sum + nums[index]);
res += findTargetSumWays(nums, index + 1, S, sum - nums[index]);
return res;
}
}
思路2：其实是一个 01 背包问题。原问题等价于： 找到 nums 的两个子集，对这个两个子集分解求和，然后作差等于 target。我们假设 P 是其中一个子集，N 是剩下的元素组成的子集。
例如： 假设 nums = [1, 2, 3, 4, 5]，target = 3，一个可能的解决方案是 +1 - 2 + 3 - 4 + 5 = 3，这里子集P = [1, 3, 5]，子集 N = [2, 4]。
那么让我们看看如何将其转换 0-1 背包问题：
因为 sum(P) - sum(N) = target，等式两边都加上 sum(nums)，得：
2 * sum(P) = target + sum(nums)。
因此，原来的问题已转化为一个求子集的和问题： 找到 nums 的一个子集 P，使得 sum(P) = (target + sum(nums)) / 2。
请注意，上面的公式已经证明 target + sum(nums)必须是偶数，否则输出为 0。
Python 代码：
class Solution:
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
size = len(nums)
ss = sum(nums)
target = ss + S
if size == 0 or target & 1:
return 0
# 除以 2
target >>= 1
# 因为题目中给出的是非负整数，因此这一步可以提前判断是否有解
if target > ss:
return 0
dp = [[0 for _ in range(target + 1)] for _ in range(size)]
# 这一步不要忘记了
dp[0][0] = 1
for j in range(target + 1):
if nums[0] == j:
dp[0][j] += 1
for i in range(1, size):
for j in range(target + 1):
# 至少是不选这个物品时候的种数
dp[i][j] += dp[i - 1][j]
if j >= nums[i]:
dp[i][j] += dp[i - 1][j - nums[i]]
return dp[-1][-1]
if __name__ == '__main__':
solution = Solution()
# nums = [1, 1, 1, 1, 1]
# S = 3
nums = [35, 25, 24, 23, 2, 47, 39, 22, 3, 7, 11, 26, 6, 30, 5, 34, 10, 43, 41, 28]
S = 49
result = solution.findTargetSumWays(nums, S)
print(result)
Java 代码：
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int n : nums)
sum += n;
return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1);
}
public int subsetSum(int[] nums, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
（本节完）
