//一開始想的是用int[]數(shù)組的dp衙猪，最后返回dp[target]
//但這個在數(shù)據(jù)量特別大的時候枫匾，可能會overflow
//比如說100個100，構(gòu)成10000闪金， target就是5000，C(100, 50) = 1.0089134454556424e+29
//能不能就是討論一個可行性嘛论颅，直接用一個boolean數(shù)組就行了
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
if (sum % 2 == 1) return false;
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= nums[i]; j--) {
if (dp[j - nums[i]]) dp[j] = true;
}
}
return dp[target];
}
}
class Solution {
//assume all numbers can be divided to two groups, positive and negative
//a is positive, b is negative
//a + |b| = sum, a + b = S => 2a = sum + S
//if there is any sol, sum + S must be even
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) sum += num;
if (sum < S || (sum + S) % 2 == 1) return 0;
//將其轉(zhuǎn)變成0-1背包問題恃疯，每個item只能選一次漏设，有多少種方法sum to target
int n = nums.length;
int target = (sum + S) / 2;
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
if (nums[i-1] == 0) { //因為數(shù)字是0，對于這個item今妄，選或不選都一樣
dp[i][0] = dp[i-1][0] * 2;
} else {
dp[i][0] = dp[i-1][0];
}
}
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] = dp[i-1][j] + dp[i-1][j - nums[i-1]];
}
}
}
return dp[n][target];
}
}
//對于空間復雜度的優(yōu)化
class Solution {
//assume all numbers can be divided to two groups, positive and negative
//a is positive, b is negative
//a + |b| = sum, a + b = S => 2a = sum + S
//if there is any sol, sum + S must be even
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) sum += num;
if (sum < S || (sum + S) % 2 == 1) return 0;
//將其轉(zhuǎn)變成0-1背包問題郑口，每個item只能選一次，有多少種方法sum to target
int n = nums.length;
int target = (sum + S) / 2;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = target; j >= nums[i]; j--) {
//如果遇到nums[i] == 0的情況蛙奖，會再加一遍
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
-
474. Ones and Zeroes
0-1背包
original probleam has only one limitation: size
now we hace two limitations
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for (String str : strs) {
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') zero++;
if (c == '1') one++;
//zero += (c - '0') ^ 1; //這一部分使用位運算會更快
//one += ('1' - c) ^ 1;
}
for (int i = m; i >= zero; i--) {
for (int j = n; j >= one; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i-zero][j-one] + 1);
}
}
}
return dp[m][n];
}
}
class Solution {
//each coin can be choosen unlimited times
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
int w = coins[i];
for (int j = w; j <= amount; j++) {
if (dp[j - w] != Integer.MAX_VALUE)
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
int w = coins[i];
for (int j = w; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
-
377. Combination Sum IV
完全背包問題
給定一個由正整數(shù)組成且不存在重復數(shù)字的數(shù)組，找出和為給定目標正整數(shù)的組合的個數(shù)琐脏。
請注意攒砖，順序不同的序列被視作不同的組合缸兔。
class Solution {
public int combinationSum4(int[] nums, int target) {
int n = nums.length;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int j = 1; j <= target; j++) {
for (int i = 0; i < n; i++) {
if (j >= nums[i]) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) {
int len = word.length();
if (i >= len && dp[i - len] && word.equals(s.substring(i-len, i))) dp[i] = true;
}
}
return dp[n];
}
}
//做了一些優(yōu)化，預先將存在的word放入set中吹艇，并限制內(nèi)層循環(huán)的len
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
int maxLen = 0;
for (String word : wordDict) {
set.add(word);
maxLen = Math.max(maxLen, word.length());
}
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int len = 0; len <= maxLen && len <= i; len++) { //j is the possible len of word
if (dp[i-len] && set.contains(s.substring(i-len, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
