目標和
力扣題目網址:目標和
這道題我們先用回溯的思想來做。首先我們設正數和為S，數組和為N，目標值為T，那么
S-(N-S)=T化簡之后可以得S=(T+N)/2即選擇的正數個數為偶數，而且N+T也為偶數，那么第一個判斷條件我們就有了，并且問題可以轉換為，背包容量為(T+N)/2，有幾種選擇正數的方式能夠填滿背包，回溯思想代碼如下，主要還是選或者不選，這里我們仍然需要用記憶化搜索，不然會超時
package day17;import java.util.Arrays;// p
// s-p
// p-(s-p)=target
// p = (s+target)/2
public class id_494_1 {public int[] NUMS;private int[][] memo;public int findTargetSumWays(int[] nums, int target) {target += Arrays.stream(nums).sum();if(target < 0 || target % 2 != 0) return 0;target /= 2;int n = nums.length;memo = new int[n][target + 1];for (int[] row : memo) {Arrays.fill(row, -1);}this.NUMS = nums;return dfs(NUMS.length - 1, target);}public int dfs(int i,int c){if(i < 0){return c == 0 ? 1 : 0;}if(memo[i][c] != -1) return memo[i][c];if(c < NUMS[i]){return memo[i][c] = dfs(i-1,c);}return memo[i][c] = dfs(i-1,c) + dfs(i-1,c-NUMS[i]);}
}
接下來我們用遞推的方式來做也就是用循環和二維數組來代替遞歸,這道題的初始化也需要我們討論，我們只需要初始化0 0處為1，因為背包容量為0的時候0個物品有1種添加方式，也就是不放物品。
package day17;import java.util.Arrays;public class id_494_2 {private int[][] f;public int findTargetSumWays(int[] nums, int target) {target += Arrays.stream(nums).sum();if(target < 0 || target % 2 != 0) return 0;target /= 2;int n = nums.length;f = new int[n+1][target + 1];f[0][0] = 1;for(int i = 0; i < n; i++){for(int j = 0; j < target+1; j++){if(j < nums[i]){f[i+1][j] = f[i][j];}else {f[i+1][j] = f[i][j] + f[i][j - nums[i]];}}}return f[n][target];}
}
簡化為一個數組的時候，我們需要倒序遍歷背包，具體解釋可以看靈茶山艾府的視頻背包問題:遍歷順序
package day17;import java.util.Arrays;public class id_494_3 {private int[] f;public int findTargetSumWays(int[] nums, int target) {target += Arrays.stream(nums).sum();if(target < 0 || target % 2 != 0) return 0;target /= 2;int n = nums.length;f = new int[target + 1];f[0] = 1;for(int i : nums){for(int j = 0; j < target + 1; j++){f[j] += f[j - i];}}return f[target];}
}
零錢兌換
力扣題目網址:零錢兌換
這道題和上一道差不多，但是這道題硬幣可以重復選擇。我們就不用回溯的思想來寫了，直接看二維數組遞推的方法。這道題需要我只有在00的地方初始化為0，其他地方初始化為int的最大值，但是在java中這樣會越界，主播我初始化為20000，這樣在最后如果找不到符合的，那么f[n][amount]的值就是我們初始化的值
package day17;import java.util.Arrays;// 完全背包
public class id_LCR103_2 {private int[][] memo;public int coinChange(int[] coins, int amount) {int n = coins.length;memo = new int[n + 1][amount + 1];for (int[] ints : memo) {Arrays.fill(ints, 20000);}memo[0][0] = 0;for(int i = 0; i < n; i++){for(int j = 0; j <= amount; j++){if(j < coins[i]){memo[i+1][j] = memo[i][j];}else {memo[i+1][j] = Math.min(memo[i][j], memo[i+1][j - coins[i]] + 1);}}}return memo[n][amount] < 20000 ? memo[n][amount] : -1;}}
我們繼續簡化為一維數組，這時候遍歷循序就需要變為正序
package day17;import java.util.Arrays;public class id_LCR103_3 {public int coinChange(int[] coins, int amount) {int n = coins.length;int[] f = new int[amount + 1];Arrays.fill(f, 20000);f[0] = 0;for(int x : coins){for(int j = x; j <= amount; j++){f[j] = Math.min(f[j], f[j - x] + 1);}}return f[amount] < 20000 ? f[amount] : -1;}
}
)
)