TargetSum [source code]
public class TargetSum {
static
/******************************************************************************/
class Solution {
static int OFS = 1000;
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length;
int[][] dp = new int[n][1 + 2 * OFS];
for (int i = 0; i < n; i++) {
for (int j = 0; j < dp[0].length; j++) {
if (i == 0) {
if (j - OFS + S == nums[0])
dp[0][j]++;
if (j - OFS + S == -nums[0])
dp[0][j]++;
} else {
int negIndex = j + nums[i];
int negPrev = negIndex >= 0 && negIndex < dp[0].length ? dp[i - 1][negIndex] : 0;
int posIndex = j - nums[i];
int posPrev = posIndex >= 0 && posIndex < dp[0].length ? dp[i - 1][posIndex] : 0;
dp[i][j] = negPrev + posPrev;
}
}
}
return dp[n - 1][0 + OFS];
}
}
/******************************************************************************/
public static void main(String[] args) {
TargetSum.Solution tester = new TargetSum.Solution();
int[][] inputs = {
{1,1,1,1,1}, {3}, {5},
{1,0}, {1}, {2},
};
for (int i = 0; i < inputs.length / 3; i++) {
int[] nums = inputs[3 * i];
int S = inputs[3 * i + 1][0], ans = inputs[3 * i + 2][0];
System.out.println (Printer.separator ());
int output = tester.findTargetSumWays (nums, S);
System.out.printf ("[%s] and %d -> %s, expected: %d\n",
Printer.array (nums), S, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
题目意思应该还是比较直接的, 而且感觉应该能用DP来做;
思考DP算法的时候的一个问题发现, 表格的另外一个维度应该是用sum来做, 但是可能的sum就老多了; 但是回头一看, note里面给了你隐藏条件, 告诉你sum不会太大, 事实上, 是告诉你nums里面所有的元素之和(不是target) 不会超过1000, 这个就是告诉了你表格的维度的上下限;
最后超时但是有惊无险的AC了, 速度是48ms (56%). 不算出色;
这个题目看起来算法很简单, 但是实际上写的时候花了老不少时间; 一个原因是因为这题DP的第二个维度, 我是定义成offset from target的, 这样就要涵盖一个[-1000, 1000]的范围; 这样计算和设计的时候始终跟默认的[0, 2000]有一个shift的差距存在, 脑子里转弯很麻烦;
另外, 注意看我这里专门把1000给提取出来, 给了一个单独的变量, 是为了debug的时候, 如果是调试的是小case, 可以把这个值调小, 这样print就可行; 这个也是一个debug的技巧;
除开这些, 这个算法还要需要注意的一个问题就是DP的initialization问题的重要性在这个算法里面一览无余; 首先你注意到, 我这里只对i==0的情况进行了init, 而对于j==0, 是没有必要init的; 即使是对于i==0的init, 其实也不trivial, 需要你真正理解这个问题的本质;
注意到body里面的main branch, 我没有对0进行特殊处理; 但是实际上是可以这么做的;
为什么想到把第二个维度定义成一个offset? 这样这个维度的总长度就比较好控制, 是固定的. 假如不定义成offset, 而是定义成一个包含S的量, 那么就很难说, 因为S的范围其实是没有给出的, 你怎么知道S +/- nums[i]到底在多大的范围以内呢;
另外这个题目做完了之后我才意识到一个问题, 这题用Bottom-Up非常的不好, 浪费了很多时间做没有必要的运算; 这题直接一个Top-Down的recursion是最好的思路;
你可能会想, 那Top-Down的memo不是难写一些吗? 你再想想呢? 这题实际上不需要写memo, 因为不同的sub call之间, 没有overlapping, 也就没有必要写memo;
editorial
Approach #1 Brute Force [Accepted]
public class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
calculate(nums, 0, 0, S);
return count;
}
public void calculate(int[] nums, int i, int sum, int S) {
if (i == nums.length) {
if (sum == S)
count++;
} else {
calculate(nums, i + 1, sum + nums[i], S);
calculate(nums, i + 1, sum - nums[i], S);
}
}
}
基本就是一个DFS暴搜; 复杂度是2^N; 跟大部分的DFS一样, 这个算法的问题是不走到最后一个leaf的位置, 是不知道当前的path是否正确的. 注意上面的这个方法是没有办法继续prune的, 因为在每一个level, sum有可能变大也有可能变小, 所以很难说;
重新看了一下题目, 所有的entry都是非负数, 所以实际上是可以prune的;
Approach #2 Recursion with memoization [Accepted]
public class Solution {
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
int[][] memo = new int[nums.length][2001];
for (int[] row: memo)
Arrays.fill(row, Integer.MIN_VALUE);
return calculate(nums, 0, 0, S, memo);
}
public int calculate(int[] nums, int i, int sum, int S, int[][] memo) {
if (i == nums.length) {
if (sum == S)
return 1;
else
return 0;
} else {
if (memo[i][sum + 1000] != Integer.MIN_VALUE) {
return memo[i][sum + 1000];
}
int add = calculate(nums, i + 1, sum + nums[i], S, memo);
int subtract = calculate(nums, i + 1, sum - nums[i], S, memo);
memo[i][sum + 1000] = add + subtract;
return memo[i][sum + 1000];
}
}
}
基本就是加了一个memoization. 不过这个作者自己称这个做法为一定的pruning. 我觉得memo这个东西按说跟pruning还是有点区别的;
Approach #3 2D Dynamic Programming [Accepted]
public class Solution {
public int findTargetSumWays(int[] nums, int S) {
int[][] dp = new int[nums.length][2001];
dp[0][nums[0] + 1000] = 1;
dp[0][-nums[0] + 1000] += 1;
for (int i = 1; i < nums.length; i++) {
for (int sum = -1000; sum <= 1000; sum++) {
if (dp[i - 1][sum + 1000] > 0) {
dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];
dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
}
}
}
return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
}
}
他这个算法跟我的算法的一个区别就是他的y坐标不是offset, 而是直接的对应target sum; 这也是为什么他最后返回的是[..][S + 1000].
另外注意他这个初始化的方法: 按理说应该这样做, 因为只有两种可能性, 所以只有两个entry需要初始化, 所以用这种直接的方法来初始化其实更加好;
discussion最优解, 讲的非常好:
@yuxiangmusic said in Java (15 ms) C++ (3 ms) O(ns) iterative DP solution using subset sum with explanation:
The recursive solution is very slow, because its runtime is exponential
The original problem statement is equivalent to:
Find a subset ofnumsthat need to be positive, and the rest of them negative, such that the sum is equal totargetLet
Pbe the positive subset andNbe the negative subset
For example:
Givennums = [1, 2, 3, 4, 5]andtarget = 3then one possible solution is+1-2+3-4+5 = 3
Here positive subset isP = [1, 3, 5]and negative subset isN = [2, 4]Then let's see how this can be converted to a subset sum problem:
sum(P) - sum(N) = target sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N) 2 * sum(P) = target + sum(nums)So the original problem has been converted to a subset sum problem as follows:
Find a subsetPofnumssuch thatsum(P) = (target + sum(nums)) / 2Note that the above formula has proved that
target + sum(nums)must be even
We can use that fact to quickly identify inputs that do not have a solution (Thanks to @BrunoDeNadaiSarnaglia for the suggestion)
For detailed explanation on how to solve subset sum problem, you may refer to Partition Equal Subset SumHere is Java solution (15 ms)
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for (int n : nums)
sum += n;
return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1);
}
public int subsetSum(int[] nums, int s) {
int[] dp = new int[s + 1];
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
Here is C++ solution (3 ms)
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int s) {
int sum = accumulate(nums.begin(), nums.end(), 0);
return sum < s || (s + sum) & 1 ? 0 : subsetSum(nums, (s + sum) >> 1);
}
int subsetSum(vector<int>& nums, int s) {
int dp[s + 1] = { 0 };
dp[0] = 1;
for (int n : nums)
for (int i = s; i >= n; i--)
dp[i] += dp[i - n];
return dp[s];
}
};
看到这里之后把我自己的解法也优化了一下:
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int n = nums.length, OFS = 0;
for (int i : nums)
OFS += i;
if ((OFS + S) % 2 == 1)
return 0;
int[][] dp = new int[n][1 + 2 * OFS];
for (int i = 0; i < n; i++) {
for (int j = 0; j < dp[0].length; j++) {
if (i == 0) {
if (j - OFS + S == nums[0])
dp[0][j]++;
if (j - OFS + S == -nums[0])
dp[0][j]++;
} else {
int negIndex = j + nums[i];
int negPrev = negIndex >= 0 && negIndex < dp[0].length ? dp[i - 1][negIndex] : 0;
int posIndex = j - nums[i];
int posPrev = posIndex >= 0 && posIndex < dp[0].length ? dp[i - 1][posIndex] : 0;
dp[i][j] = negPrev + posPrev;
}
}
}
return dp[n - 1][0 + OFS];
}
}
到了37(58). 差别不是特别明显;
discussion一个比较有意思的说法:
@Chidong said in Short Java DP Solution with Explanation:
public class Solution {
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for(int i: nums) sum+=i;
if(s>sum || s<-sum) return 0;
int[] dp = new int[2*sum+1];
dp[0+sum] = 1;
for(int i = 0; i<nums.length; i++){
int[] next = new int[2*sum+1];
for(int k = 0; k<2*sum+1; k++){
if(dp[k]!=0){
next[k + nums[i]] += dp[k];
next[k - nums[i]] += dp[k];
}
}
dp = next;
}
return dp[sum+s];
}
}
基本思路是类似的, 不过优化了空间占用; 另外他的填表的时候的assemble的顺序也是一个Bottom-Up(不是指填表iterate的顺序), 这个顺序在上面discussion最优解的那个subset问题, 以及在NLP的HMM算法的时候都见识过了;
submission最优解就是之前discussion最优解那个转换成subsum问题的解法;
Problem Description
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-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
There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
Difficulty:Medium
Total Accepted:42.2K
Total Submissions:96.3K
Contributor:[email protected]
Companies
googlefacebook
Related Topics
dynamic programmingdepth-first search
Similar Questions
Expression Add Operators