算法动态规划（五）-背包问题2
⚠️今天继续我们的0-1背包问题。
👉👀💬今日练习（一）一和零（LeetCode-474）。
给定m个0、n个1和一个只由0、1构成字符串的数组，使用给定的m个0和n个1拼成数组中的字符串的最大数量，每个0和1最多使用一次。举例：
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3输出: 4解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。输入: Array = {"10", "0", "1"}, m = 1, n = 1输出: 2解释: 我们可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
🙇思路：
此题依然是0-1背包问题。
状态定义：dp[i][j][k]表示，字符串数组[0 , i]区间内的字符串，可以用j个0、k个1表示的最大数量。
转态转移：数组中第i个元素选择或不选择两种状态。
不选。dp[i][j][k] = dp[i-1][j][k] 前i-1个数组元素可以用j、k个0或1可以表示的最大数量。
选择。用cn[]数组来表示第i个字符串中0、1的个数，状态转移方程为：dp[i][j][k] = dp[i-1][j-cn[0]][k-cn[1]] + 1 前i-1个数组元素，只能用剩下的(j-cn[0])个0和(k-cn[1])个1可以表示出的最大数量。
综合，最后的状态转移方程表示为：
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-cn[0]][k-cn[1]] + 1)
最终输出：dp[len-1][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];// i 从1开始，保证规划中上行是存在的。for(int i=1;i<=len;i++){int[] cn = count(strs[i-1]);for(int j=0;j<=m;j++){for(int k=0;k<=n;k++){// 不论之后的分析是啥，至少是上一行的头顶的这个数量。dp[i][j][k] = dp[i-1][j][k];if(j>=cn[0] && k>=cn[1]){dp[i][j][k]=Math.max(dp[i-1][j][k],dp[i-1][j-cn[0]][k-cn[1]]+1);}}}}return dp[len][m][n];}private int[] count(String str){int[] cn = new int[2];for(char c:str.toCharArray()){cn[c-'0']++;}return cn;}
🙋空间优化
🙇思路：
在上面解法中，我们依旧是只参考了当前行的上一行，所以这儿我们对于空间的优化就是一个思路降维。采用二维数组来进行逆向填表。
代码：
public int findMaxForm(String[] strs, int m, int n) {int len = strs.length;int[][] dp = new int[m+1][n+1];// i 从1开始，保证规划中上行是存在的。for(int i=1;i<=len;i++){int[] cn = count(strs[i-1]);for(int j=m;j>=cn[0];j--){for(int k=n;k>=cn[1];k--){dp[j][k]= Math.max(dp[j][k],dp[j-cn[0]][k-cn[1]]+1);}}}return dp[m][n];}private int[] count(String str){int[] cn = new int[2];for(char c:str.toCharArray()){cn[c-'0']++;}return cn;}
👉👀💬今日练习（二）目标和（LeetCode-494）。
给定一个非负整数数组nums，和一个目标数S，数组中每一个数前都可以添加+或-符号，添加完后使得数组的和为S，找出可以添加符号的组合数。举例：
输入：nums[1,2,3,4,5] S=3输出：3解释：可以添加符号的情况有以下3种-1+2+3+4-5=3-1-2-3+4+5=31-2+3-4+5=3dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]
🙇思路：
错误思路：
一开始我的思路是第i个数选择-或者选择+，状态方程为：dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]不难看出，状态方程中j+nums[i]的边界我们无法获知了。
正确的思路：
仔细省题，我们不难发现题目中无非就是有m个正数加n个负数，最后的结果为S，这道题其实和我们之前做过的分割等和子集（LeetCode-416）很像。416是让找出两个等和子集，而这道题换个思路就是，找出两个子集使得和为S。所以，这儿我们将符号为+的容量定为X，符号为负的容量定为Y，数组的总和为sum，我们可以得到X+Y=sum；X-Y=S。基于这两个等式，我们可以得到X=(S+sum)/2；且S+sum必须为偶数。
通过题目的思路转换，最后我们就将本题转换成一个简单的0-1背包问题，即从数组nums中找出一些数，使得和为X，找出所有的组合方式。
状态定义：dp[i][j]表示，数组[0 , i]区间内可以找到和为j的组合数。
转态转移：数组中第i个元素选择或不选择两种状态。
不选。dp[i][j] = dp[i-1][j]前i-1个数可以找到和为j的数量。
选择。dp[i][j] = dp[i-1][j-nums[i]]。前i-1个数可以找到和为(j-nums[i])的数量。
综合，最后的状态转移方程表示为：
dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]]。
最终输出：dp[len][X]。
代码（我们这儿就直接就选择空间优化的做法）：
public int findTargetSumWays(int[] nums, int S) {int len = nums.length;int sum = 0;for(int num:nums){sum+=num;}if(((S+sum)&1) == 1){return 0;}// 目标和不可能大于总和if (S>sum){return 0;}int X = (S+sum)/2;int[] dp = new int[X+1];dp[0]=1;for(int i=0;i<len;i++){for(int j=X;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[X];}
不积跬步，无以至千里。
文章有帮助的话，点个转发、在看呗
。
谢谢支持哟 (*^__^*)
END
👇