力扣AC：组合总和IV - 动态规划

题目链接

组合总和IV

题目描述

实现代码

该题动态规划思想跟零钱兑换II 思想类似，区别在于一个是组合问题一个是排列问题；在本题中，{1,3}和{3,1}是两个方案，因此需要先遍历金额在遍历零钱；

实现代码：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        int len = nums.length;
        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];
    }
}