跳转至

3183. 达到总和的方法数量 🔒

题目描述

给定 无限 数量的面值为 1，2，6 的硬币，并且 只有 2 枚硬币面值为 4。

给定一个整数 n ，返回用你持有的硬币达到总和 n 的方法数量。

因为答案可能会很大，将其 取模 109 + 7。

注意 硬币的顺序并不重要，[2, 2, 3] 与 [2, 3, 2] 相同。

 

示例 1：

输入：n = 4

输出：4

解释：

有四种组合：[1, 1, 1, 1]，[1, 1, 2]，[2, 2]，[4]。

示例 2：

输入：n = 12

输出：22

解释：

注意 [4, 4, 4] 不是 一个有效的组合，因为我们无法使用 4 三次。

示例 3：

输入：n = 5

输出：4

解释：

有四种组合：[1, 1, 1, 1, 1]，[1, 1, 1, 2]，[1, 2, 2]，[1, 4]。

 

提示：

  • 1 <= n <= 105

解法

方法一：动态规划（完全背包）

我们可以先忽略硬币 $4$，定义硬币数组 coins = [1, 2, 6]，然后使用完全背包的思想，定义 $f[j]$ 表示使用前 $i$ 种硬币凑成金额 $j$ 的方案数，初始时 $f[0] = 1$，然后我们遍历硬币数组 coins，对于每一种硬币 $x$，我们遍历 $x$ 到 $n$ 的金额，更新 $f[j] = f[j] + f[j - x]$。

最后 $f[n]$ 就是使用硬币 $1, 2, 6$ 凑成金额 $n$ 的方案数，然后如果 $n \geq 4$，我们考虑选择一个硬币 $4$，那么方案数就是 $f[n] + f[n - 4]$，如果 $n \geq 8$，我们再考虑选择两个硬币 $4$，那么方案数就是 $f[n] + f[n - 4] + f[n - 8]$。

注意答案的取模操作。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是金额。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def numberOfWays(self, n: int) -> int:
        mod = 10**9 + 7
        coins = [1, 2, 6]
        f = [0] * (n + 1)
        f[0] = 1
        for x in coins:
            for j in range(x, n + 1):
                f[j] = (f[j] + f[j - x]) % mod
        ans = f[n]
        if n >= 4:
            ans = (ans + f[n - 4]) % mod
        if n >= 8:
            ans = (ans + f[n - 8]) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numberOfWays(int n) {
        final int mod = (int) 1e9 + 7;
        int[] coins = {1, 2, 6};
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int x : coins) {
            for (int j = x; j <= n; ++j) {
                f[j] = (f[j] + f[j - x]) % mod;
            }
        }
        int ans = f[n];
        if (n >= 4) {
            ans = (ans + f[n - 4]) % mod;
        }
        if (n >= 8) {
            ans = (ans + f[n - 8]) % mod;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numberOfWays(int n) {
        const int mod = 1e9 + 7;
        int coins[3] = {1, 2, 6};
        int f[n + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int x : coins) {
            for (int j = x; j <= n; ++j) {
                f[j] = (f[j] + f[j - x]) % mod;
            }
        }
        int ans = f[n];
        if (n >= 4) {
            ans = (ans + f[n - 4]) % mod;
        }
        if (n >= 8) {
            ans = (ans + f[n - 8]) % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func numberOfWays(n int) int {
    const mod int = 1e9 + 7
    coins := []int{1, 2, 6}
    f := make([]int, n+1)
    f[0] = 1
    for _, x := range coins {
        for j := x; j <= n; j++ {
            f[j] = (f[j] + f[j-x]) % mod
        }
    }
    ans := f[n]
    if n >= 4 {
        ans = (ans + f[n-4]) % mod
    }
    if n >= 8 {
        ans = (ans + f[n-8]) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function numberOfWays(n: number): number {
    const mod = 10 ** 9 + 7;
    const f: number[] = Array(n + 1).fill(0);
    f[0] = 1;
    for (const x of [1, 2, 6]) {
        for (let j = x; j <= n; ++j) {
            f[j] = (f[j] + f[j - x]) % mod;
        }
    }
    let ans = f[n];
    if (n >= 4) {
        ans = (ans + f[n - 4]) % mod;
    }
    if (n >= 8) {
        ans = (ans + f[n - 8]) % mod;
    }
    return ans;
}

方法二：预处理 + 动态规划（完全背包）

我们可以先预处理出 $1$ 到 $10^5$ 的所有金额的方案数，然后根据 $n$ 的大小直接返回对应的方案数：

  • 如果 $n < 4$，直接返回 $f[n]$；
  • 如果 $4 \leq n < 8$，返回 $f[n] + f[n - 4]$；
  • 如果 $n \geq 8$，返回 $f[n] + f[n - 4] + f[n - 8]$。

注意答案的取模操作。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是金额。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
m = 10**5 + 1
mod = 10**9 + 7
coins = [1, 2, 6]
f = [0] * (m)
f[0] = 1
for x in coins:
    for j in range(x, m):
        f[j] = (f[j] + f[j - x]) % mod


class Solution:
    def numberOfWays(self, n: int) -> int:
        ans = f[n]
        if n >= 4:
            ans = (ans + f[n - 4]) % mod
        if n >= 8:
            ans = (ans + f[n - 8]) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private static final int MOD = 1000000007;
    private static final int M = 100001;
    private static final int[] COINS = {1, 2, 6};
    private static final int[] f = new int[M];

    static {
        f[0] = 1;
        for (int x : COINS) {
            for (int j = x; j < M; ++j) {
                f[j] = (f[j] + f[j - x]) % MOD;
            }
        }
    }

    public int numberOfWays(int n) {
        int ans = f[n];
        if (n >= 4) {
            ans = (ans + f[n - 4]) % MOD;
        }
        if (n >= 8) {
            ans = (ans + f[n - 8]) % MOD;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int m = 1e5 + 1;
const int mod = 1e9 + 7;
int f[m + 1];

auto init = [] {
    f[0] = 1;
    int coins[3] = {1, 2, 6};
    for (int x : coins) {
        for (int j = x; j < m; ++j) {
            f[j] = (f[j] + f[j - x]) % mod;
        }
    }
    return 0;
}();


class Solution {
public:
    int numberOfWays(int n) {
        int ans = f[n];
        if (n >= 4) {
            ans = (ans + f[n - 4]) % mod;
        }
        if (n >= 8) {
            ans = (ans + f[n - 8]) % mod;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const (
    m   = 100001
    mod = 1000000007
)

var f [m]int

func init() {
    f[0] = 1
    coins := []int{1, 2, 6}
    for _, x := range coins {
        for j := x; j < m; j++ {
            f[j] = (f[j] + f[j-x]) % mod
        }
    }
}

func numberOfWays(n int) int {
    ans := f[n]
    if n >= 4 {
        ans = (ans + f[n-4]) % mod
    }
    if n >= 8 {
        ans = (ans + f[n-8]) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const m: number = 10 ** 5 + 1;
const mod: number = 10 ** 9 + 7;
const f: number[] = Array(m).fill(0);

(() => {
    f[0] = 1;
    const coins: number[] = [1, 2, 6];
    for (const x of coins) {
        for (let j = x; j < m; ++j) {
            f[j] = (f[j] + f[j - x]) % mod;
        }
    }
})();

function numberOfWays(n: number): number {
    let ans = f[n];
    if (n >= 4) {
        ans = (ans + f[n - 4]) % mod;
    }
    if (n >= 8) {
        ans = (ans + f[n - 8]) % mod;
    }
    return ans;
}

评论