背包DP(數位成本和為目標值的最大數字+完全平方數+零錢兌換+盈利計劃+最后一塊石頭的重量+目標和+1和0）

example 1:

class Solution {
    public String largestNumber(int[] cost, int target) {
     int [][]dp=new int[10][target+1];
     for(int i=0;i<=target;i++){
         dp[0][i]=Integer.MIN_VALUE;
     }
     int [][]form=new int[10][target+1];
     dp[0][0]=0;
     for(int i=1;i<=9;i++){
         for(int j=0;j<=target;j++){
             if(j<cost[i-1]){
             dp[i][j]=dp[i-1][j];
             form[i][j]=j;
             }
             else{
              if(dp[i-1][j]>dp[i][j-cost[i-1]]+1){
                  dp[i][j]=dp[i-1][j];
                  form[i][j]=j;
              }
              else{
                  dp[i][j]=dp[i][j-cost[i-1]]+1;
                  form[i][j]=j-cost[i-1];
              }
             }
         }
     }
     if(dp[9][target]<0)return "0";
     StringBuffer res=new StringBuffer();
     int i=9,j=target;
     while(i>0){
         if(j==form[i][j])i--;
         else{
             res.append(i);
             j=form[i][j];
         }
     }
     return res.toString();
    }
}

example 2:

class Solution {
    public int numSquares(int n) {
    int []dp=new int[n+1];
    for(int i=1;i<=n;i++){
    int minn = Integer.MAX_VALUE;
        for(int j=1;j*j<=i;j++){
            minn = Math.min(minn, dp[i - j * j]);
        }
        dp[i]=minn+1;
    }
    return dp[n];
    }
}

**example 3：**零錢兌換

class Solution {
    public int change(int amount, int[] coins) {
    int []dp=new int[amount+1];
    dp[0]=1;
    for(int i=1;i<=coins.length;i++){
        for(int j=coins[i-1];j<=amount;j++){         
                dp[j]+=dp[j-coins[i-1]];       
        }
    }
    return dp[amount];
    }
}

example 4：

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
    int mod=(int)Math.pow(10,9)+7;
    int [][][]dp=new int[profit.length+1][n+1][minProfit+1];
    dp[0][0][0]=1;
    for(int i=1;i<=profit.length;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=minProfit;k++){
                dp[i][j][k]=dp[i-1][j][k];
                if(group[i-1]<=j)dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])])%mod;
            }
        }
    }
    int res=0;
    for(int i=0;i<n+1;i++){
        res=(res+dp[profit.length][i][minProfit])%mod;
    }
    return res;
    }
}

問題轉化為：
我們可以吧石頭分成兩堆，一堆是重量較大的，一堆重量較小，那么每次從兩堆石頭中各挑選一個石頭相撞，撞剩下的石頭放回原堆，那么怎么使得最后剩下的石頭重量最小？

首先考慮一個問題：
較大的那一堆石頭重量大于較小的那一堆，設較小的重量為neg，另一堆重量則是sum-neg，如此得出sum-neg>=neg,neg<=sum/2,當neg=sum/2的時候剩余最后一塊一定是0重量，那么只要使得背包容量從sum/2遞減到0，找出能滿足題中給出的石頭和能不能滿足背包容量，能即為答案，進而轉化為背包的目標和問題，

因此我們設定一個背包容量0-sum/2，看能否裝滿，所以每到一個石頭如果裝他，就去看有沒有裝滿j-stones[i-1]這個容量，如果前面的石頭能裝成這個容量如果不裝，就需要看前i-1是否已經裝滿了 j 容量，最后只要反向查找出滿足題中陣列的最大目標和為多少？即可得出最后的答案

class Solution {
    public int lastStoneWeightII(int[] stones) {
     int sumall=0;
     for(int i=0;i<stones.length;i++){
         sumall+=stones[i];
     }
     int sum=sumall;
     sumall/=2;//分成兩堆石頭 互相碰，小的碰沒了大的碰完再放回去，結果就等于兩堆石頭差，這個差值>=0,由此推匯出小的那堆石頭<=sumall/2
     boolean [][]dp=new boolean[stones.length+1][sumall+1];
     dp[0][0]=true;
     for(int i=1;i<=stones.length;i++){
         for(int j=0;j<=sumall;j++){
             dp[i][j]=dp[i-1][j];
             if(j>=stones[i-1])dp[i][j]=dp[i-1][j]||dp[i-1][j-stones[i-1]];//設定一個背包容量看能否裝滿，所以每到一個石頭如果裝他，就去看有沒有裝滿j-stones[i-1]這個容量，如果不裝，就需要看前i-1是否已經裝滿了j容量
         }
     }
     for(int i=sumall;i>=0;i--){//找出最大的j結果就等于總和減-2*j
         if(dp[stones.length][i])return sum-2*i;
     }
     return 0;
    }
}

example 5：

同上面問題一樣：
我們設添加負號的數的和為neg，正好的數和則為sum-neg，那么問題就轉化為了sum-neg-neg=target，即neg=（sum-target）/2的方案數，由此我們轉化成目標和等于neg的方案數問題，sum和target都是已知量

我們設定一個dp[i][j]前i個數目標和為j的方案數
所以每次遇到一個數，都有要不要選他的問題，選他的方案數=dp [i-1] [j-nums[i]] ,不選他的方案數dp[i-1][j]，所以若num[i]>j,不能選i這個數，num[i]<=j則方案數=兩者相加

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sumall=0;
        for(int i=0;i<nums.length;i++){
            sumall+=nums[i];
        }

     int dif=sumall-target;
     if(dif<0||dif%2==1)return 0;
     dif/=2;
     int [][]dp=new int[nums.length+1][dif+1];
     dp[0][0]=1;
     for(int i=1;i<=nums.length;i++){
         for(int j=0;j<=dif;j++){
             dp[i][j]=dp[i-1][j];
             if(j>=nums[i-1])dp[i][j]+=dp[i-1][j-nums[i-1]];
         }
     }
     return dp[nums.length][dif];
    }
}

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
       int [][][]dp=new int[strs.length+1][m+1][n+1];
       for(int i=1;i<=strs.length;i++){
           int[]count=countzeroandone(strs[i-1]);
           for(int j=0;j<=m;j++){
               for(int k=0;k<=n;k++){
                   dp[i][j][k]=dp[i-1][j][k];
                   if(j>=count[0]&&k>=count[1])
                   dp[i][j][k]=Math.max(dp[i-1][j][k],dp[i-1][j-count[0]][k-count[1]]+1);
               }
           }
       }
       return dp[strs.length][m][n];
    }
    public int []countzeroandone(String s){
        int []res=new int[2];
        for(char ch:s.toCharArray()){
            res[ch-'0']++;
        }
        return res;
    }
}