leetcode/377CombinationSumIV

Combination Sum IV

找出满足条件组合的次数

my solution

没脸写出来

best solution

func combinationSum4(nums []int, target int) int {
    if target <= 0 {
        return 0
    }
    dp := make([]int, target+1)
    dp[0] = 1

    for i := 0; i <= target; i++ {
        for _, num := range nums {
            if i-num >= 0 {
                dp[i] += dp[i-num]
            }
        }
    }
    return dp[target]
}

0 1 = 1
1 1 = 1
2 1 1 = 2
3 2 1 1 = 4
4 4 2 1 = 7

不太好描述这个规律, 有点类似于 “万丈高楼平地起”, 简单来说就是一个迭代/包含的过程

比较关键的地方在于循环中的 if (感觉是废话 = = )

我想过, 是否会出现一种情况, 这种情况通过了判断, 但是实际上不正确

比如 当 i = 3 的时候, num = 2, 通过了判断, 但是此时没有 1 那么就无法组成 4

这种情况成立么? 答案是否定的, 因为 2 中的次数就包含了有 1, 如果没有 1, 2 也将会是 0

假设 P(x) 为 x 所包含的次数, 上述解法就是 P(x) = P(x - 1) + … + P(1) (等式右侧每项参数都位于nums中)

(感觉越描越黑了 - - )