背包问题
01背包是经典的动态规划问题，本篇文章记录leetcode中出现的经典案例
该图片截图自 @code_lover_forever
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
int sum = 0;
for(int i:nums){
sum += i;
}
if(sum%2 == 1){
return false;
}
int target = sum/2;
boolean[] dp = new boolean[target+1];
dp[0] = true;
for(int num:nums){
for(int i=target;i>=0;i–){
if(i – num >=0){
dp[i] = dp[i]||dp[i-num];
}
}
}
return dp[target];
}
}
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i:nums){
sum+=i;
}
int diff = sum – target;
if(diff < 0 || diff%2!=0){
return 0;
}
/** 问题转化成求组成和为diff/2有多少种组合 */
int n = diff/2;
int[] dp = new int[n+1];
dp[0] = 1;
for(int i:nums){
for(int j=n;j>=i;j–){
dp[j] = dp[j] + dp[j-i];
}
}
return dp[n];
}
}
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for(String s:strs){
int zero_cnt = 0;
int one_cnt = 0;
for(char c:s.toCharArray()){
if(c == ‘0’){
zero_cnt++;
}else{
one_cnt++;
}
}
for(int i=m;i>=zero_cnt;i–){
for(int j=n;j>=one_cnt;j–){
dp[i][j] = Math.max(dp[i][j],dp[i-zero_cnt][j-one_cnt] + 1);
}
}
}
return dp[m][n];
}
}
class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[] dp = new int[amount+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i=1;i<=amount;i++){
for(int coin:coins){
if(i<coin || dp[i-coin] == Integer.MAX_VALUE){
continue;
}else{
dp[i] = Math.min(dp[i],dp[i-coin]+1);
}
}
}
return dp[amount]==Integer.MAX_VALUE?–1:dp[amount];
}
}
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp,n);
dp[0] = 0;
for(int i=1;i<=n;i++){
for(int j=1;j*j<=i;j++){
dp[i] = Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount+1];
dp[0] = 1;
for(int coin:coins){
for(int i=1;i<=amount;i++){
if(i<coin){
continue;
}else{
dp[i] += dp[i-coin];
}
}
}
return dp[amount];
}
}
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordset = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n+1];
dp[0] = true;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
if(dp[j] ==true &&wordDict.contains(s.substring(j,i))){
dp[i] = true;
}
}
}
return dp[n];
}
}