LeetCode 494 Target Sum
链接：https://leetcode.com/problems/target-sum/
方法1：DFS + memo
时间复杂度：O(n * sum)
想法：经典题目，所以决定把所有做法全写一遍。第一种写法是DFS+memo，很多情况下DP的题可以用DFS+memo写成递归形式。这种写法其实想法非常简单，dfs携带(int[] nums, int index, int cur, int target)，表示的是遍历到了index这个地方，现在算出来的值是cur，然后从这个地方到最后一共有多少种方案。所以对于每一层dfs，res = dfs(nums, index + 1, cur + nums[index], target) + dfs(nums, index + 1, cur - nums[index], target);，表示这个地方放+或-，然后进入下一个index的搜索。
代码：
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;
}
}
方法2：普通DP
时间复杂度：O(n * sum)
想法：把上面的普通递归写成普通DP。dp[i][j]表示在算到下标i的时候，求出来结果是j的方案有多少种。那么很显然dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]，因为dp[i][j]里面的这个j，要么目前这个元素前面放的是+号，要么是-号，倒推回去上一个index，就一定只有dp[i - 1][j - nums[i]]和dp[i - 1][j + nums[i]]两个状态可以变到这里来。当然这个题放负号可能导致中间结果是负的，因此做好offset。
代码：
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];
}
}
方法3：背包DP
时间复杂度：O(n * sum)
想法：需要对这个问题进行重新分析。我反正是没想出来，方法来自花花酱的解答https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-494-target-sum/。假设原本拿到一个数组，里面有若干数字，题目说了里面数字全部>=0。因此假设原来的数的集合里面，后来前面加+的数集合是P，后来前面放-的数集合是N。那么sum(P) - sum(N) = target，则2 * sum(P) = target + sum(P) + sum(N) = target + sum of array。因此背包target + sum of array的一半。
代码：
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];
}
}
方法4：背包DP的优化
时间复杂度：O(n * sum)
想法：可以继续做背包的优化，可以压缩到一维数组。这个也是比较常见的背包DP优化，对于物品的重量倒着遍历。
代码：
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];
}
}
LeetCode 377 Combination Sum IV
链接：https://leetcode.com/problems/combination-sum-iv/
方法1：DFS + memo
时间复杂度：O(sum(target/num_i))，分析来自https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-377-combination-sum-iv/
想法：就是说从题干中读题意，意识到他所说的方案是考虑元素顺序的，比方说[1,1,2]和[1,2,1]和[2,1,1]，他认为是三种不同的方案。那这样就比较简单了，假设说nums = [1,2,3], target = 4，那么组成target=4的方案是可以由之前的方案推出来的，组成target=4的所有方案，就是target=1的各方案后面放3，target=2的方案后面放2，和target=3的方案后面放3合起来。因此可以有递归和递推两种写法。对于递归，target=4的时候递归调用target=3的结果，target=3的子问题又调target=2的结果。这次调完之后target=4这一问题还要调target=2的结果，因此每个target对应的值都会有被重复调用的可能，使用记忆化数组避免重复计算。但因为在递归当中，res += dfs(nums, target - nums[i])，每次减掉的是nums[i]，而不用真的-1-1的这么调，因此理论上来说应该是要比一个一个往上推的DP快一些，但可能因为这题数据规模比较小，我也没观察到明显差别。
代码：
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;
}
}
方法2：DP
时间复杂度：O(target * n)
想法：上面那个就是递归写法，这里无非就是把它写成递推的形式。
代码：
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];
}
}
LeetCode 518 Coin Change 2
链接：https://leetcode.com/problems/coin-change-2/
方法：DP
时间复杂度：O(amount * n)
想法：递归的写法我就不写了，这种DP应该都能用递归+memo做。把这个题在这里搬出来就是为了跟上一题形成对比，体会两个题之间的区别。复习上一题的时候我就想到了Facebook tag里面的这一道题。直接贴代码。这个题的外循环是coin，内循环是amount，而上一题完全相反，为什么呢？
首先，两题的差别在于，对于第二题，[1,1,2]与[1,2,1]被认为是一种方案，所以这个题才是有一点Combination的看法。既然是一种方案，就没有我在上面那道题所说的，对于求target的所有方案，可以严格按照target之前的这些方案在后面加一个数构造出来，既然是combination，顺序就不再重要，因此上一问的做法放在这里是不对的。
第二点，下面这种写法并不是故意先枚举coins再循环amount，下面这种写法源于背包DP。因为原本来说，DP的思路是dp[i][j]为前i个数，能够构成j的方法总数，对于做背包DP的时候，我们是先循环i再循环j的，下面这个代码无非是发现dp数组可以用滚动数组的方法优化空间复杂度，因此变成了这样，背包DP为什么要先循环i，这里就为什么要先循环coin。
代码：
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];
}
}
