题目
image.png
题解
题解1
class Solution {
public int findTargetSumWays(int[] nums, int S) {
return dfs(nums, S, 0, 0);
}
private int dfs(int[] nums, int S, int index, int sum) {
if (index == nums.length) {
if (sum == S) {
return 1;
}
return 0;
}
// return Math.max(dfs(nums, S, index + 1, sum + nums[index]), dfs(nums, S, index + 1, sum - nums[index]));
return dfs(nums, S, index + 1, sum + nums[index]) + dfs(nums, S, index + 1, sum - nums[index]);
}
题解2
0-1背包问题
但是这样处理不对
// 状态 数组个数，目标和
// 选择 + -
// dp意义 dp[i][j] 使用前i个能达到j和的个数/方法数 1<=i<=n, 0<=j<=s
// base case dp[0][..]=0, dp[...][1]=1
// 公式 dp[i][j]=dp[i-1][j-nums[i]]/[+] + dp[i-1][j+nums[i]]/[-]
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
int[][] dp = new int[n + 1][S+1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= S; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j+nums[i-1]];
} else if (j+nums[i-1] > S) {
dp[i][j] = dp[i-1][j-nums[i-1]];
} else {
dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j+nums[i-1]];
}
}
}
return dp[n][S];
}
}
问题：
有减法，所以和会出现负数
这样的思路的接下去解答可参考
https://leetcode-cn.com/problems/target-sum/solution/dong-tai-gui-hua-si-kao-quan-guo-cheng-by-keepal/
image.png
题解3
想要转换为0-1背包问题，直接使用是不行的，需要转换
这个问题可以转化为一个子集划分问题，而子集划分问题又是一个典型的背包问题
image.png
// sum(A) = (sum+S)/2 = target 子集划分，存在几个子集A
// dp[i][j] 前i个能达到j和 的方法数
// i选择或是不选择
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
int target = (sum + S) / 2;
int[][] dp = new int[n + 1][target+1];
// dp[..][0] = 1
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
// dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]]);
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
错误
image.png
image.png
改进
// sum(A) = (sum+S)/2 = target 子集划分，存在几个子集A
// dp[i][j] 前i个能达到j和 的方法数
// i选择或是不选择
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
if (n == 1) {
if (Math.abs(nums[0]) == Math.abs(S)) {
return 1;
}
return 0;
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
int target = (sum + S) / 2;
int[][] dp = new int[n + 1][target+1];
// dp[..][0] = 1
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
// dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]]);
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
改进
// 状态 数组个数，目标和
// 选择 + -
// dp意义 dp[i][j] 使用前i个能达到j和的个数/方法数 1<=i<=n, 0<=j<=s
// base case dp[0][..]=0, dp[...][1]=1
// 公式 dp[i][j]=dp[i-1][j-nums[i]]/[+] + dp[i-1][j+nums[i]]/[-]
// sum(A) = (sum+S)/2 = target 子集划分，存在几个子集A
// dp[i][j] 前i个能达到j和 的方法数
// i选择或是不选择
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
if (n == 1) {
if (Math.abs(nums[0]) == Math.abs(S)) {
return 1;
}
return 0;
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
if (sum < S || (sum + S) % 2 != 0) {
return 0;
}
int target = (sum + S) / 2;
return solver(nums, target);
}
public int solver(int[] nums, int target) {
int n = nums.length;
int[][] dp = new int[n + 1][target+1];
// dp[..][0] = 1
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
// dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]]);
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
}
}
image.png
和416的只需要true和false不同，这边j需要从0开始遍历
// sum(A) = (sum+S)/2 = target 子集划分，存在几个子集A
// dp[i][j] 前i个能达到j和 的方法数
// i选择或是不选择
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
if (n == 1) {
if (Math.abs(nums[0]) == Math.abs(S)) {
return 1;
}
return 0;
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
if (sum < S || (sum + S) % 2 != 0) {
return 0;
}
int target = (sum + S) / 2;
return solver(nums, target);
}
public int solver(int[] nums, int target) {
int n = nums.length;
int[][] dp = new int[n + 1][target+1];
// dp[..][0] = 1
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= target; j++) {
if (j < nums[i-1]) {
dp[i][j] = dp[i-1][j];
} else {
// dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]]);
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
}
}
}
return dp[n][target];
}
}
