Leetcode 377 组合求和四

  public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++)
        {
            for (int num: nums) {
                if(i-num<0) continue;
                dp[i]+=dp[i-num];
            }
        }
        return dp[target];
   } 

Leetcode 494 目标和

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[][] dp=new int[nums.length][2001];
        //init
        dp[0][1000+nums[0]]=1;
        //可能为0
        dp[0][1000-nums[0]]+=1;

        for(int i=1;i<nums.length;i++)
        {
            for(int j=0;j<=2000;j++)
            {
                if(j-nums[i]>=0)
                {
                    dp[i][j]+=dp[i-1][j-nums[i]];
                }
                if(j+nums[i]<=2000)
                {
                    dp[i][j]+=dp[i-1][j+nums[i]];
                }
            }
        }
        return S<Integer.MAX_VALUE&&1000+S<=2000?dp[nums.length-1][1000+S]:0;
    }
}

Leetcode 518

class Solution {
    public int change(int amount, int[] coins) {
        if(coins.length==0) return amount==0?1:0;
        int[][] dp=new int[coins.length][amount+1];
        //init 
        dp[0][0]=1;
        for(int j=1;j<=amount;j++)
        {
            if(j%coins[0]==0) dp[0][j]=1;
        }
        for(int i=1;i<coins.length;i++)
            for(int j=0;j<=amount;j++)
            {
                dp[i][j]=dp[i-1][j];
                if(j-coins[i]>=0) dp[i][j]+=dp[i][j-coins[i]];
            }
        return dp[coins.length-1][amount];
    }
    public int change(int amount, int[] coins) {
        /*if(coins.length==0) return amount==0?1:0;
        int[] dp=new int[amount+1];
        //init 
        dp[0]=1;
        for(int j=1;j<=amount;j++)
        {
            if(j%coins[0]==0) dp[j]=1;
        }
        for(int i=1;i<coins.length;i++)
            for(int j=0;j<=amount;j++)
            {
                //dp[i][j]=dp[i-1][j];
                if(j-coins[i]>=0) dp[j]+=dp[j-coins[i]];
            }
        return dp[amount];*/
    }
}