494. 目标和

题目

链接

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i =0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum<Math.abs(target)){
            return 0;
        }
        if((sum-target)%2==1){
            return 0;
        }
        
        int subNum = (sum-target)/2;
        int[] dp = new int[subNum+1];
        dp[0] = 1;
        for(int i =0;i<nums.length;i++){
            for(int j = dp.length-1;j>=nums[i];j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[subNum];
    }
}

474. 一和零

题目

链接

代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j] 0为i个，1为j个，的最大子集数
        int[][] dp = new int[m+1][n+1];
        for(int k =0;k<strs.length;k++){
            int[] MN = countMN(strs[k]);
            for(int i =m;i>=MN[0];i--){
                for(int j =n;j>=MN[1];j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-MN[0]][j-MN[1]]+1);
                }
            }
        }   
        return dp[m][n];
    }

    public int[] countMN(String str){
        char[] arr = str.toCharArray();
        int m = 0;
        int n = 0;
        for(int i =0;i<arr.length;i++){
            if(arr[i]=='0'){
                m++;
            }else{
                n++;
            }
        }
        return new int[]{m,n};
    }

}

518. 零钱兑换 II

题目

链接

代码

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