算法萌新如何学好动态规划（3）( 八 ) 本文是「动态规划」系列文章的第三篇

解题思路本题与上一题唯一的区别在于，上一题要求的「凑成总金额最少需要的硬币个数」，而本题求的是「凑成总金额的方案数」。因此只需稍微改动一下「DP 状态意义」以及「DP 转移方程」即可。
由于本题的硬币依然可以无限取，因此仍然使用「完全背包」模型进行求解。定义
文章插图
表示仅考虑前 i 类硬币，其总金额为 j 时的组合数。因此可以得到如下「DP 转移方程」：
文章插图
初始条件为，
文章插图
。接下来使用「完全背包」滚动数组版本的代码即可，具体细节如下。
C++ 代码实现class Solution {public:vector f;int change(int amount, vectorf[0] = 1;for(int i = 0; i < coins.size(); i++)for(int j = coins[i]; j <= amount; j++)f[j] += f[j-coins[i]];return f[amount];}};?474. 一和零题目描述在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1 。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
示例 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" 。 提示

给定 0 和 1 的数量都不会超过 100 。
给定字符串数组的长度不会超过 600 。

解题思路简要概括一下题意，一共有 m 个 0 ， n 个 1 。现有 n 个字符串，其中第 i 个字符串需要

文章插图
个 0 ，

文章插图
个 1 ，现问最多可以拼出多少个字符串。
这个题看似可能和背包没太大关系，但仔细思考之后，还是可以发现此题的本质仍然是选取若干个字符串，使其 0 和 1 的个数之和分别小于等于 m 和 n ，因此仍然是一道背包问题。并且由于每一个字符串只能选一次，因此是一道「0/1 背包」问题。
我们仿照「0/1 背包」的思路，定义

文章插图
表示对于前 i 个字符串，一共有 j 个 0 和 k 个 1 时，能拼出的最大字符串个数。
可以发现对比「0/1 背包」的基础模型，我们将「DP 状态」从二维扩展到了三维，主要原因在于本题有两个参数，分别是 0 和 1 的个数。可以理解为有两个背包，要装两种东西，但本质不变，只需在原先基础上扩展一维即可。
因此我们可以仿照原先的基础模型，得到如下「DP 转移方程」：