LC.P377[组合总和IV]

方法一：记忆化搜索

这道题本质是LC.P70[爬楼梯]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    int[] cache;
    int[] nums;

    public int combinationSum4(int[] nums, int target) {
        cache = new int[target + 1];
        this.nums = nums;
        Arrays.fill(cache, -1);
        return dfs(target);
    }

    private int dfs(int i) {
        if (i == 0) return 1;
        if (cache[i] != -1) return cache[i];
        int ans = 0;
        for (int x : nums) {
            if (x <= i) {
                ans += dfs(i - x);
            }
        }
        return cache[i] = ans;
    }
}
  • 时间复杂度：$O(target \times n)$
  • 空间复杂度：$O(target)$

方法二：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int x : nums) {
                if (x <= i) {
                    f[i] += f[i - x];
                }
            }
        }
        return f[target];
    }
}
  • 时间复杂度：$O(target \times n)$
  • 空间复杂度：$O(target)$