动态规划-刷题
分割等和子集（01背包）
问题
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
题目难度：中等
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。分析
求将数组分成2个子集，并且要求两个子集的元素和相等。也就是说要求每个子集的和为总和 sum 的一半 mid，每个元素只能出现一次🤔这不是刚跟我们做的的01背包很像吗？我们逐步分析一下
如果我们把它看成01背包问题，元素都改如何对应的
物品数量有多少个，这个很明显就是元素的个数，数组nums的len长度
背包重量，我们把单个子集看成一个背包，那背包的重量不就是这个子集的和 mid 吗，也就是说物品的重量为 num 的元素值
物品的价值，因为要求子集的总和为 mid，那 num 的元素值也为 物品的价值
我们将这些信息带入01背包的公式
01背包公式：dp[i, c] = max(dp[i - 1, c], dp[i - 1, c - wgt[i - 1]] + val[i - 1])
带入公式：
不放入元素：dp[i, c] = dp[i - 1, c]
放入元素：dp[i, c] = max(dp[i - 1][c], dp[i - 1][c - num[i - 1]] + num[i - 1])
边界和转移方向
i 为物品数量，即元素数量
c 为背包剩余容量，最大值为 mid
如果背包放不下元素，最大值为dp[i - 1, c]
依赖上一个物品的价值，所以双层循环正序遍历即可
如果总和不能整除，则数组不能被分成两个和相等的子集
求解
除了一些边界值的确定，还需要注意我们求单个子集的和mid，而不是总和sum
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
int len = nums.length;
for (int i = 0; i < len; i++) {
sum += nums[i];
}
int rema = sum % 2;
if (rema != 0) {
return false;
}
int mid = sum / 2;
int[][] dp = new int[len + 1][mid + 1];
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= mid; j++) {
if (nums[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
}
}
}
if (dp[len][mid] == mid) {
return true;
}
return false;
}力扣执行，我们可以看出内存是浪费的，我们可以将二维的数组优化为一维数组
时间复杂度：因为使用了双层循环，O(n) = len * mid = n^2
空间复杂度：使用了dp二维数组，O(n) = len * mid = n^2
优化
优化思路跟优化01背包思路一样，优化掉 i ，内层循环递减
public boolean canPartitionOptimize(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
int len = nums.length;
for (int i = 0; i < len; i++) {
sum += nums[i];
}
int rema = sum % 2;
if (rema != 0) {
return false;
}
int mid = sum / 2;
int[] dp = new int[mid + 1];
for (int i = 1; i <= len; i++) {
for (int j = mid; j >= 1; j--) {
if (nums[i - 1] <= j) {
dp[j] = Math.max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]);
}
}
}
if (dp[mid] == mid) {
return true;
}
return false;
}力扣执行，通过理解结果我们可以看到，优化后，内存占用减少了
时间复杂度：因为使用了双层循环，O(n) = len * mid = n^2
空间复杂度：使用了dp一维数组，数组长度可以看做 n，O(n) = mid = n
目标和（01背包）
问题
给你一个非负整数数组
nums和一个整数target。向数组中的每个整数前添加
'+'或'-'，然后串联起所有整数，可以构造一个 表达式 ：
例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于
target的不同 表达式 的数目。难度：中等
示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 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 +1 + 1 + 1 + 1 - 1 = 3示例 2：
输入：nums = [1], target = 1 输出：1
分析
找变量
分析题目中存在的关系，每个整数只能有一个符号，要么是‘+’ 要么是 ’-‘，要求得target，那只需要用加号部分的 减掉 减号部分的，就是我们需要的结果，我们假定加号和为left，减号和为right，
我们可以得到公式：left - right = target
又因为：left + right = sum
通过两个公式我们可以得出：right = (sum - target) / 2
这里我们为什么要转换right，因为right是个变量，targht和sum分别是常量，我们最好找变量与常量之间的关系，这里用left也是可以的。
01背包转换
为什么是01背包问题，因为数组的元素只能被使用一次【相当于物品只能被放入一次】
这里我们最终求得结果是得到target的种类数，我们假设dp[i, j] 为target的种类数 【背包问题，i是物品i，j是物品容量，值为价值】，这个i是元素数，j 是target，作为背包的大小。dp[i, j] 就是在第 i 个元素，有几种方式可以达到容量为 j 的背包。这里大家可能会认为，在01背包里物品可以选择是否放入啊，那跟这个题怎么对应呢，我们可以这样考虑，如果i元素不放入，也就是说不属于left，那它肯定属于right部分，所以不需要考虑不放入后，元素会用不起来。
最优子结构
能放入元素，即 j >= num[i]
放入元素：dp[i - 1][j - nums[i]]
不放入元素： dp[i - 1, j]
总数：dp[i, j] = dp[i - 1, j] + dp[i - 1][j - nums[i]]
不能放入元素，即 j < num[i]
dp[i, j] = dp[i - 1, j]
边界和转移方向
i 为物品数量
j为背包容量大小 = (sum - target)/2
nums的总和小于target，则不需要处理
left 不能被2整除，不用处理
初始化, dp[0][0] = 1，元素为0个，元素和为0，只有1中方法
i 为0的一整行，意味着元素个数为0，不需要考虑，所以 i 的起始值为 1
j为0的一整列，代表求和为0的方案数，有意义，需要考虑，j的起始值为0
求解
public int findTargetSumWays(int[] nums, int target) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
// sum的总数小于target 、 left 不能被2整除
if (sum < target || (sum - target) % 2 != 0) {
return 0;
}
int packSize = Math.abs((sum - target) / 2);
int dp[][] = new int[len + 1][packSize + 1];
dp[0][0] = 1;
for (int i = 1; i <= len; i++) {
// 注意，num的下标是从0开始，所以需要-1
int num = nums[i - 1];
for (int j = 0; j <= packSize; j++) {
// 无法放入
if (j < num) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
}
}
}
return dp[len][packSize];
}优化
优化思路跟优化01背包思路一样，优化掉 i ，内层循环递减
public int findTargetSumWays_Optimize(int[] nums, int target) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
// sum的总数小于target 、 left 不能被2整除
if (sum < target || (sum - target) % 2 != 0) {
return 0;
}
int packSize = Math.abs((sum - target) / 2);
int dp[] = new int[packSize + 1];
dp[0] = 1;
for (int i = 1; i <= len; i++) {
// 注意，num的下标是从0开始，所以需要-1
int num = nums[i - 1];
for (int j = packSize; j >= 0; j--) {
// 无法放入
if (j >= num) {
dp[j] += dp[j - num];
}
}
}
return dp[packSize];
}一和零（01背包）
问题
https://leetcode.cn/problems/ones-and-zeroes/description/
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100
分析
背包问题
为什么是背包问题？
我们可以将这个子集的个数理解成一个大背包，m和n分别是限制背包容量的两个限制
通过分析，我们要取到 n 个元素的最大子集，需要找到前 n - 1个元素的最大子集，大问题可以拆分成小问题求解
01背包 or 完全背包
因为数组元素只能出现一次，所以是01背包，但是01背包里我们只有一个容量大小的限制，但是这个题有m和n的数量限制，所以这里求解要用一个三维数组求解
dp
dp[i][m][n] 为前 i - 1个元素，在0的数量限制为m，1的数量限制为n的条件下，最大的子集数量
最优子结构
这里需要统计子集中0、1的个数，这里我们假设0的个数 zeroNums、1的个数 oneNums
当子集不满足0、1个数的限制时，最大子集数为前 i - 1个元素的最大子集数
dp[i][j][k] = dp[i - 1][j][k]
当子集满足0、1个数的限制时，可以选择将子集放入背包，也可以不放入，最大的子集数为
不放入元素的最大子集数：dp[i - 1][j][k]
放入元素的最大子集数：dp[i - 1][j - zeroNums][k - oneNums] + 1
取最大值：dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - zeroNums][k - oneNums] + 1)
边界和转移方向
初始化
dp数组的长度为 len+1,m+1,n+1
结果为 dp[len][m][n]
转移方向（循环）
第一层循环是元素数组（物品数量），起始值为1，取元素用下标 i - 1
第二层循环为0的个数（背包的m大小限制），起始值为0，此值为0仅代表限制0的个数为0，所以为0是有意义
第三层循环为1的个数（背包的n大小限制），起始值为0，此值为0仅代表限制1的个数为0，所以为0是有意义
边界
需要探讨三个数值，元素个数、m、n
当元素个数为0，m和n的限制为0，最大子集个数为0
m和n的大小限制
求解
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int dp[][][] = new int[len + 1][m + 1][n + 1];
for (int i = 1; i <= len; i++) {
int[] res = countNum(strs[i - 1]);
int zeroNums = res[0];
int oneNums = res[1];
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
// 判断
if (j >= zeroNums && k >= oneNums) {
dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeroNums][k - oneNums] + 1);
} else {
dp[i][j][k] = dp[i - 1][j][k];
}
}
}
}
return dp[len][m][n];
}
/**
* 统计字符串中0和1的个数
* @param str
* @return
*/
public int[] countNum(String str) {
int[] arr = new int[2];
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '0') {
arr[0] = arr[0] + 1;
} else if (str.charAt(i) == '1') {
arr[1] = arr[1] + 1;
}
}
return arr;
}优化
优化做的两步
去掉外层循环（元素的for循环）
内层循环从大到小
public int findMaxForm_optimize(String[] strs, int m, int n) {
int len = strs.length;
int dp[][] = new int[m + 1][n + 1];
for (int i = 1; i <= len; i++) {
int[] res = countNum(strs[i - 1]);
int zeroNums = res[0];
int oneNums = res[1];
for (int j = m; j >= 0; j--) {
for (int k = n; k >= 0; k--) {
// 判断
if (j >= zeroNums && k >= oneNums) {
dp[j][k] = Math.max(dp[j][k], dp[j - zeroNums][k - oneNums] + 1);
} else {
dp[j][k] = dp[j][k];
}
}
}
}
return dp[m][n];
}零钱兑换II（完全背包）
问题
https://leetcode.cn/problems/coin-change-ii/description/
给你一个整数数组
coins表示不同面额的硬币，另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回
0。假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1示例 2：
输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。示例 3：
输入：amount = 10, coins = [10] 输出：1
分析
完全背包
这里硬币数量无限个，我们可以把硬币值看做物品，背包大小为总金额。因为物品数量不限放入个数，所以为完全背包。
这里我们设dp[i][j] 为第 i-1 个物品，能凑成金额 j 的组合数
最优子结构
当硬币的金额大于剩余金额不放入时，组合数为
dp[i - 1][j]
当硬币的金额大于剩余金额
不放入的最大方案数：dp[i - 1][j]
放入的最大方案数：dp[i][j - coin] + 1 （这里取的是i，是因为硬币可以重复选择）
总数：dp[i - 1][j] + dp[i - 1][j - coin]
初始化&状态转移
循环
第一层循环为硬币循环（物品循环），硬币循环从1开始
第二层循环为总金额循环（背包容量），金额从 0 开始
初始化
当硬币数量为0时，凑得金额为非0时，没有方案
当凑得金额为0时，硬币数量为非0时，没有方案
当硬币数量和凑得金额都为0时，方案有1种
求解
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length + 1][amount + 1];
dp[0][0] = 1;
for (int i = 1; i <= coins.length; i++) {
int coin = coins[i - 1];
for (int j = 0; j <= amount; j++) {
// 硬币的金额大于剩余最大金额
if (coin > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - coin];
}
}
}
return dp[coins.length][amount];
}优化
public int change_optimize(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 1; i <= coins.length; i++) {
int coin = coins[i - 1];
for (int j = 0; j <= amount; j++) {
// 硬币的金额大于剩余最大金额
if (coin <= j) {
dp[j] = dp[j] + dp[j - coin];
}
}
}
return dp[amount];
}最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/description/
问题
给定两个字符串
text1和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回0。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
分析
动规分析
要求最长公共子序列的长度，我们可以先求得前 text1 前 i -1个元素、text2前 j - 1 个元素的最长公共子序列的长度
假设 dp[i][j] 数组为 text1长度为 i、text2长度 j 的最长公共子序列的长度，i、j 的最大值分别为len(text1) + 1, len(text2) + 1
最优子结构
当 text1[i - 1] == text2[j - 1] 字符相等时，最长公共字符列的长度在 dp[i - 1][j - 1]的最长公共子序列长度 + 1
当 text1[i - 1] != text2[j - 1] 字符不相等时，最长公共子序列的长度取 dp[i - 1][j] 和 dp[i][j - 1] 的最大值，与 dp[i - 1][j - 1]就没关系了，因为前两者的数值已经将 dp[i - 1][j - 1] 参与对比
初始化和状态转移
初始化
当取text1长度为0时，最长公共子序列长度为0
当取text2长度为0时，最长公共子序列长度为0
dp[0][0] = 0
状态转移，text1从第一个字符开始遍历，text2从第一个字符开始遍历
举例推演即可
求解
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
for (int i = 1; i <= text1.length(); i++) {
char c1 = text1.charAt(i - 1);
for (int j = 1; j <= text2.length(); j++) {
char c2 = text2.charAt(j - 1);
if (c1 == c2) {
// 如果字符相同，则最长子序列增加
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.length()][text2.length()];
}