leetcode-combination-sum-iv

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/combination-sum-iv/

　　给你一个数组和一个target值，求数组中的组合的和等于target，121和112，211视为不同的。

题目分析

　　动态规划不仅可以解决最优值问题，可以解决很多计数类问题。想解决目标值为target的问题要借助于目标值比target小的子问题。结果数组为dp，所求的为dp[target]。dp[i] = dp[i] + dp[i - x]，x为nums数组中的值，意思是想解决dp[i]，如果dp[i-x]已经解决了，再把x值加入这一组合中就成为一个解了。注意下，dp［0］为1，因为这是起始情况，比如数组只有一个元素1，target也为1，dp[0]显然得为1的情况下，结果dp[1]才能为1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    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 x : nums) {
                if(i >= x) {
                    dp[i] += dp[i-x];
                }
            }
        }
        return dp[target];
    }
}

　　时间复杂度O(target * num.length)