Leetcode-0/1 knapsack problem
Ref:link
416. Partition Equal Subset Sum (Medium)
If you see a problem asks you to find two equal sums in the array, this means you need to find the half of all elements’ sum in the array. For this problem, we need to partition equal subset sum. At first, we calculate the sum of all elements. If we can find the half of sum in the input array, we can partition it into equal subset sum. Therefore, the problem is find the sum of elements which is equal to the target value. Obviously, this is 0/1 knapsack problem.
Here we use 1D array to represent dp array instead of 2D array. dp[i] means if the sum of some elements in the input array is i. For the second for loop, we iterate from the end of the array, because this can guarantee the value will not be larger. If we start from the start of the array, values will be larger than the correct answer.
If the sum of the whole array is m. Time complexity is O(mn). Space complexity is O(m). Here is the link.
public boolean canPartition(int[] nums) {
int ans =0;
for(int num:nums)ans+=num;
if(ans%2!=0)return false;
int target = ans/2;
int[]dp = new int[target+1];
for(int i =1;i<nums.length+1;i++){
for(int j =target;j>=1;j--){
if(nums[i-1]<=j){
dp[j]=Math.max(dp[j],dp[j-nums[i-1]]+nums[i-1]);
}
}
}
return dp[target]==target;
}
494. Target Sum (Medium)
I think this problem should be difficult but not medium. When I saw this problem, my first thought is recursion and backtracking. But the below solution is very nice and it’s difficult for me to get this solution.
Assume we have nums={a,b,c,d} and a+b-c-d=S. Assume a+b+c+d=total. We can get below relationships.
a+b-c-d=S
a+b=S+c+d
a+b+c+d=S+2*(c+d)
c+d=(total-S)/2
We can also get a+b=(total+S)/2. Both ways are correct. Now, we change the original problem to another problem which we are familiar with. Find the target sum in the input array. This time is a little different. We don’t want the sum but the number of ways to get the sum. dp[i] means the number of ways to get the sum i for all elements in nums. At first, let’s treat dp as 2D array. For nums[i]<=target, we can add it or not add it to the sum. If we add it, there are dp[i-1][j-nums[i]] ways to get the sum. If we don’t add it, there are dp[i-1][j] to get the sum. Therefore, dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]]. And we transform it to 1D dp array. It will be dp[j] = dp[j]+dp[j-nums[i]].
If the value of target is m. Time complexity is O(mn). Space complexity is O(m). Here is the link.
public int findTargetSumWays(int[] nums, int S) {
int total = 0;
for(int num:nums)total+=num;
if((total+S)%2!=0||total<S)return 0;
int target = (total+S)/2;
int[]dp = new int[target+1];
dp[0]=1;
int ans = 0;
for(int i =0;i<nums.length;i++){
for(int j = target;j>=nums[i];j--){
dp[j] = dp[j]+dp[j-nums[i]];
}
}
return dp[target];
}
474. Ones and Zeroes (Medium)
public int findMaxForm(String[] strs, int m, int n) {
int[][]dp = new int[m+1][n+1];
for(String str:strs){
int zero = 0;
int one = 0;
for (char c : str.toCharArray()){
if(c == '0')
++zero;
else
++one;
}
for(int i = m;i>=0;i--){
for(int j =n;j>=0;j--){
if(i>=zero && j>=one)
dp[i][j] = Math.max(dp[i][j],dp[i-zero][j-one]+1);
}
}
}
return dp[m][n];
}
322. Coin Change (Medium)
This is a 01-backpack problem. coins are items we have. amount is the value we need to achieve. The difference is we can use coins without limitation.
But we need to achieve the exact value of amount.
First of all, we need to initialize all values except dp[0] to amount+1. dp[0]=0, because according to this problem’s description, if amount is 0, we need to return 0.
Why do we initialize all values to amount+1? Because this is the value that we cannot take as the answer. This problem assumes the minimal value of one coin is 1.
Therefore, the number of coins to get the value amount is at most amount(each coin’s value is 1). If we find dp[amount]==amount+1, this means that amount of money cannot be made up by any combination of the coins, we need to return -1.
dp[i] means the fewest number of coins that we can make up amount i, so dp[amount] is our answer. dp function is dp[i] = Math.min(dp[i],dp[i-coins[j]]+1). For each amount, we iterate three icons to check if we can get a fewer number for this amount. If we can’t, dp[i] is still dp[i]. If we can, dp[i] will be updated to dp[i-coins[j]]+1.
Time complexity is O(amount*n). Space complexity is O(amount). Here is the link.
public int coinChange(int[] coins, int amount) {
int[]dp = new int[amount+1];
for(int i =1;i<amount+1;i++)dp[i]=amount+1;
for(int i =1;i<amount+1;i++){
for(int j = 0 ;j<coins.length;j++){
if(coins[j]<=i){
dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount]==amount+1?-1:dp[amount];
}
518. Coin Change 2 (Medium)
In last problem, we find the fewest number of coins to make up amount. In this problem, we need to find all possible ways to make up amount. Obviously, we can use backtrack to solve this problem. But we can also use dp to solve it.
At first, let’s build a 2D dp array. dp[i][j] means the number of combinations that make up j with first i icons. For dp[i][j] and coins[i], there are two ways to get amount j: use coins[i] at least once or don’t use coins[i]. If we use coins[i], there are dp[i][j-coins[i]] ways. If not, there are dp[i-1][j] ways. Therefore, dp function should be: dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j]. But we also need to consider about the situation that j==coins[i]. If j==coins[i], we can also use this dp function, but we need to make sure the value of dp[i][j-coins[i]] is 1. dp[i][j-coins[i]] is dp[i][0].
Now, we find we only need dp[i-1] for dp[i], so we can use 1D array to solve this problem.
Time complexity is O(amount*n). Space complexity is O(amount). Here is the link.
public int change(int amount, int[] coins) {
int[]dp = new int[amount+1];
dp[0]=1;
for(int j =0;j<coins.length;j++){
for(int i =1;i<amount+1;i++){
if(i>=coins[j])
dp[i] += dp[i-coins[j]];
}
}
return dp[amount];
}
139. Word Break (Medium)
This problem is similar to the last problem. In this problem, we need to use some words to make up a string.
At first, let’s build a 2D array. dp[i][j] means whether we can use first i words to make up s.substring(0,j). If we can, we need to check the value of dp[i-1][j-word[i].length()]. If it’s true, we can make it. So we can also use 1D array. Dp function is dp[i] = dp[i-word[i].length()].
But let’s think about from another way. We still use dp and 1D array. In each iteration of the input string, we check if we can make up this substring.
We check from the tail of the substring. If we find wordDict contains s.substring(j,i) and dp[j]=true, this means we can make up this substring. dp[i]=true.
Time complexity is O(n^2). n is the length of input string. Space complexity is O(m+n). m is the size of input list. Here is the link.
public boolean wordBreak(String s, List<String> wordDict) {
boolean[]dp = new boolean[s.length()+1];
dp[0]=true;
HashSet<String>set = new HashSet();
for(String word:wordDict)set.add(word);
for(int i=1;i<s.length()+1;i++){
for(int j =i;j>=0;j--){
if(dp[j] && set.contains(s.substring(j,i)))
dp[i] = true;
}
}
return dp[s.length()];
}
377. Combination Sum IV (Medium)
Obviously, we can also use dp and backtrack to solve this problem. This problem is similar to 518. The difference is we need to reverse two for loops. If we don’t reverse these two for loops, the answer is corresponding to the situation that different sequences are counted as one combination.
Therefor, for each value, we need to consider all dp[i-num]. This will cover all sequences.
Time complexity is O(target*n). Space complexity is O(target). Here is the link.
public int combinationSum4(int[] nums, int target) {
int[]dp = new int[target+1];
dp[0] = 1;
for(int i = 1;i<target+1;i++){
for(int num:nums){
if(num<=i)
dp[i]+=dp[i-num];
}
}
return dp[target];
}