数的划分

[编程题]数的划分

热度指数：4997 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将整数 n 分成 k 份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。

例如： n=7,k=3 ，下面三种分法被认为是相同的。

$1，1，5;$

$1，5，1;$

$5，1，1;$

问有多少种不同的分法, 答案对 10⁹ + 7 取模。

数据范围： $6 \lt n \le 5000，2 \le k \le 1000$

进阶：空间复杂度 $O(nk)$ ，时间复杂度 $O(nk)$

示例1

输入

7,3

输出

示例2

输入

6,2

输出

算法知识视频讲解

Python3

今天也要学习

class Solution:
    def divideNumber(self , n: int, k: int) -> int:
        mod = 10**9 + 7
        # dp[i][j] 表示将整数i分成j份
        dp = [[0]*(k+1) for _ in range(n+1)]    
        for i in range(k+1):
            dp[i][i] = 1

        for i in range(1,n+1):
            for j in range(1,min(i,k)+1):
                dp[i][j] = (dp[i-j][j] + dp[i-1][j-1]) % mod
        return dp[n][k]

发表于 2025-01-13 16:10:10 回复(0)