//一开始想的是用int[]数组的dp，最后返回dp[target]
//但这个在数据量特别大的时候，可能会overflow
//比如说100个100，构成10000， target就是5000，C(100, 50) = 1.0089134454556424e+29
//能不能就是讨论一个可行性嘛，直接用一个boolean数组就行了
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;
//将其转变成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) { //因为数字是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];
}
}
//对于空间复杂度的优化
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;
//将其转变成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];
}
}
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];
}
}
//做了一些优化，预先将存在的word放入set中，并限制内层循环的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];
}
}
