DP动态规划笔记

第一题-力扣377

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：采用动态规划方法，计算 dp[target] 。

import java.util.*;
public class LeetCode377 {
    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(num <= i){
                    dp[i] += dp[i-num];
                }
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        LeetCode377 lc = new LeetCode377();
        Scanner sc = new Scanner(System.in);
        String inputString = sc.nextLine();
        String stringArray[] = inputString.split(" ");
        int num[] = new int[stringArray.length];
        for (int i = 0; i < stringArray.length; i++) {
            num[i] = Integer.parseInt(stringArray[i]);
        }
        int target = sc.nextInt();
        int result = lc.combinationSum4(num,target);
        System.out.println(result);
    }
}