#Java #动态规划
Feeling and experiences：
给你一个非负整数数组 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
这道题首先想到的是用回溯来做，因为就只有加减两种，要么取减法，要么取加法。
代码如下：
class Solution {
int count=0;//全局变量！
public int findTargetSumWays(int[] nums, int target) {
//用回溯来做
back(nums,target,0,0);
return count;
}
//back方法
public void back(int[] nums,int target,int index,int sum){
//如果遍历到了最后：
if(index == nums.length){ //注意 最后一个数要遍历完（所以要在最后一个数的后面）
if(sum == target){
count++;
}
}else{
//回溯加法
back(nums,target,index+1,sum+nums[index]);
//回溯减法
back(nums,target,index+1,sum-nums[index]);
}
}
}虽然代码易懂，好想到，但是时间复杂度高，且在此章节还是要用动态规划。
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
// 计算所有数字的和
for (int num : nums) {
sum += num;
}
// 计算和与目标值之间的差值
int diff = sum - target;
// 如果差值是负数或者不是偶数，则不存在解决方案
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, neg = diff / 2;
// 创建动态规划表
int[][] dp = new int[n + 1][neg + 1];
// 初始化动态规划表
dp[0][0] = 1;
// 填充动态规划表
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
// 计算不包含当前数字的情况
dp[i][j] = dp[i - 1][j];
// 如果可以加上当前数字，则累加上这种情况
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
// 返回结果
return dp[n][neg];
}
}
计算数组总和：首先，计算数组?nums?中所有元素的总和?sum。
确定剩余数：计算?sum?-?target。这一步是为了找出需要通过减法（即视为负数）得到的数的总和。
检查剩余数的奇偶性：如果?sum?-?target?是负数或奇数，那么问题无解。负数意味着目标和比所有数的总和还大，奇数意味着无法通过整数的加减组合得到目标和。
初始化动态规划数组：创建一个二维数组?dp，其中?dp[i][j]?表示在前?i?个数中选择一些数作为负数，使得这些负数的总和为?j?的方法数。
填充动态规划数组：
? 初始化?dp[0][0]?=?1，表示没有选择任何数字时，和为?0?的方法只有一种。
? 对于每个数?nums[i]?和每个可能的和?j，更新?dp[i][j]。有两种情况：
? 不使用?nums[i]：此时方法数为?dp[i-1][j]。
? 使用?nums[i]（作为负数）：如果?j?>=?nums[i]，方法数增加?dp[i-1][j-nums[i]]。
返回结果：dp[n][neg]?是最终答案，其中?n?是数组的长度，neg?是?(sum?-?target)?/?2?的值。
给你一个二进制字符串数组 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 。
要先确定dp数组的含义，才能进行递推：
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// dp[i][j] 表示最多有 i 个 0 和 j 个 1 时的字符串的最大数量
int[][] dp = new int[m + 1][n + 1];
int oneNum, zeroNum;
// 遍历每个字符串
for (String str : strs) {
oneNum = 0;
zeroNum = 0;
// 统计字符串中 0 和 1 的数量
for (char ch : str.toCharArray()) {
if (ch == '0') {
zeroNum++;
} else {
oneNum++;
}
}
// 倒序遍历，以避免重复计算
for (int i = m; i >= zeroNum; i--) {
for (int j = n; j >= oneNum; j--) {
// 更新 dp 表，决定是否选择当前字符串
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
// 返回最终结果
return dp[m][n];
}
}
?初始化动态规划数组：dp[i][j]?表示在最多使用?i?个?0?和?j?个?1?的情况下，能构成的最大子集数量。
?遍历字符串数组：对于每个字符串，计算其中?0?和?1?的数量。
? 动态规划状态转移：对于每个字符串，更新动态规划表。如果当前字符串的?0?和?1?数量分别为?zeroNum?和?oneNum，那么对于每个?i?>=?zeroNum?和?j?>=?oneNum，检查是否将当前字符串加入子集中可以得到更大的子集数量。
? 倒序更新：动态规划表需要从大到小更新，以避免在更新过程中使用到本轮已经更新过的值，从而保证每个字符串只被考虑一次。
这道题我认为关键在于怎么写dp数组，dp数组含义怎么理解。
理解到了，递推其实并不难：
? 我们从?m?到?zeroNum，从?n?到?oneNum?倒序遍历。对于每对?(i,?j)，我们有两个选择：
? 不包含当前字符串：此时子集的大小保持为?dp[i][j]。
? 包含当前字符串：如果包含当前字符串，子集大小将增加?1，但我们需要使用?zeroNum?个?0?和?oneNum?个?1。因此，新的子集大小为?dp[i?-?zeroNum][j?-?oneNum]?+?1。
? 我们取这两种选择中的最大值来更新?dp[i][j]。
“一双桨悠懒，
一绵江风微拂素罗衫”
Fighting！
?