LeetCode 494 Target Sum
Link: leetcode.com/problems/ta…
Method 1: DFS + Memo
Time complexity: O(n * sum) Idea: classic topic, so I decided to write all the practices. The first one is DFS+ Memo, and in many cases DP problems can be written recursively using DFS+ Memo. DFS carries (int[] nums, int index, int cur, int target), which tells you how many options there are from index to the end. So for each level, res = DFS (nums, index + 1, cur + nums[index], target) + DFS (nums, index + 1, cur-nums [index], target); , which means that this place is + or -, and then the next index search. Code:
class Solution {
private int[][] memo = new int[1010][2010];
public int findTargetSumWays(int[] nums, int target) {
return dfs(nums, 0, 0, target);
}
private int dfs(int[] nums, int index, int cur, int target) {
if (memo[index][cur + 1000] != 0) {
return memo[index][cur + 1000] - 1;
}
if (index == nums.length) {
if (cur == target) {
memo[index][cur + 1000] = 2;
return 1;
}
memo[index][cur + 1000] = 1;
return 0;
}
int res = dfs(nums, index + 1, cur + nums[index], target) + dfs(nums, index + 1, cur - nums[index], target);
memo[index][cur + 1000] = res + 1;
return res;
}
}
Copy the codeMethod 2: Ordinary DP
Time complexity: O(n * sum) Idea: Write the ordinary recursion above as ordinary DP. Dp [I][j] is the number of ways in which the result is j at the subscript I. Dp [I][j] = dp[i-1][j] + dp[i-1][j] + dp[i-1][j] = dp[i-1][j] + dp[i-1][j] + dp[i-1][j] + dp[i-1] There must be only two states dp[i-1][j-NUMs [I]] and DP [i-1][j + NUMs [I]]. Of course, if you put a negative sign in this problem, you might get a negative intermediate result, so make the offset. Code:
class Solution { public int findTargetSumWays(int[] nums, int target) { int n = nums.length; int sum = 0; for (int num : nums) sum += num; if (sum < Math.abs(target)) { return 0; } int doubleSum = sum << 1; int[][] dp = new int[n][doubleSum + 1]; if (nums[0] == 0) { dp[0][sum] = 2; } else { dp[0][sum - nums[0]] = 1; dp[0][sum + nums[0]] = 1; } for (int i = 1; i < n; i++) { for (int j = 0; j <= doubleSum; j++) { if (j - nums[i] >= 0) { dp[i][j] += dp[i - 1][j - nums[i]]; } if (j + nums[i] <= doubleSum) { dp[i][j] += dp[i - 1][j + nums[i]]; } } } return dp[n - 1][sum + target]; }}Copy the codeMethod 3: Backpack DP
Idea: This problem needs to be reanalyzed. I didn’t want to come out, it’s from flower sauce solutions is zxi.mytechroad.com/blog/dynami… . So let’s say you have an array of numbers, and they say all of them are greater than or equal to 0. So let’s say that the original set of numbers, the set of numbers followed by a plus is P, and the set of numbers followed by a minus is N. Sum (P) = target + sum(P) + sum(N) = target + sum of array So knapsack target + half sum of array. Code:
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0, n = nums.length;
target = Math.abs(target);
for (int num : nums) sum += num;
if (sum < target || (target + sum) % 2 != 0) {
return 0;
}
int aim = (target + sum) / 2;
int[][] dp = new int[n + 1][aim + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= aim; w++) {
dp[i][w] = dp[i - 1][w];
if (w - nums[i - 1] >= 0) {
dp[i][w] += dp[i - 1][w - nums[i - 1]];
}
}
}
return dp[n][aim];
}
}
Copy the codeMethod 4: Optimization of knapsack DP
Idea: Can continue to do knapsack optimization, can be compressed to a one-dimensional array. This is also a common backpack DP optimization, traversing backwards for the weight of the item. Code:
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0, n = nums.length;
target = Math.abs(target);
for (int num : nums) sum += num;
if (sum < target || (target + sum) % 2 != 0) {
return 0;
}
int aim = (target + sum) / 2;
int[] dp = new int[aim + 1];
dp[0] = 1;
for (int num : nums) {
for (int w = aim; w >= num; w--) {
dp[w] += dp[w - num];
}
}
return dp[aim];
}
}
Copy the codeLeetCode 377 Combination Sum IV
Link: leetcode.com/problems/co…
Method 1: DFS + Memo
Time complexity: O (sum (target/num_i)), the analysis from zxi.mytechroad.com/blog/dynami… Reading the passage, he realized that the scheme he was talking about considered the order of elements, for example [1,1,2] and [1,2,1] and [2,1,1]. He thought there were three different schemes. Said that this relatively simple assumptions nums = [1, 2, 3], target = 4, then the form target = 4 solutions can be before the launch, of all the scheme target = 4, is placed behind the scheme 3 target = 1, 2, placed behind target = 2 solutions Combined with target=3. So you can write it recursively or recursively. For recursion, target=4 recursively calls target=3, target=3 subproblem calls target=2. Target =4 and target=2 after this call, so each value of target can be called again. Use memorized arrays to avoid double counting. In this recursion, res += DFS (nums, target-nums [I]) is subtracted by nums[I], so in theory it should be faster than DP that is incremented one by one. I don’t see a significant difference. Code:
class Solution {
int res = 0;
int[] memo = new int[1010];
public int combinationSum4(int[] nums, int target) {
return dfs(nums, target);
}
private int dfs(int[] nums, int target) {
if (memo[target] != 0) {
return memo[target] - 1;
}
if (target == 0) {
memo[0] = 2;
return 1;
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= target) {
res += dfs(nums, target - nums[i]);
}
}
memo[target] = res + 1;
return res;
}
}
Copy the codeMethod 2: DP
Time complexity: O(Target * n) Thought: The above is the recursion, here is just to write it recursively. Code:
class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i <= target; i++) { for (int num : nums) { if (i >= num) { dp[i] += dp[i - num]; } } } return dp[target]; }}Copy the codeLeetCode 518 Coin Change 2
Link: leetcode.com/problems/co…
Methods: the DP
Time complexity: O(amount * n) Thought: I will not write recursively, this DP should be able to recurse +memo. I want to put this problem out here just to make a contrast, to feel the difference between the two problems. When REVIEWING the last question, I thought of this question in the Facebook tag. Post code directly. The outer loop is coin and the inner loop is amount. First of all, the difference between the two questions is that for the second question, [1,1,2] and [1,2,1] are considered as a solution, so this question is a bit of Combination. Since it is a scheme, there is no such thing as I said in the above question. For all schemes to get target, it can be constructed by adding a number after them in strict accordance with the previous schemes. Since it is a combination, the order is no longer important, so the approach in the previous question is not right here. Second, the following is not intended to enumerate coins recycle amount first. The following is derived from backpack DP. Because originally, the thinking of DP is DP [I] [j] for the former the I number, total number of methods can constitute a j, backpack to do DP, we are one of the first cycle I recycle j, the code below is found DP array can optimize the space complexity, using the method of rolling array thus became so, backpack DP why I first cycle, Here’s why we loop coins first. Code:
class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; }}Copy the code