数的划分

[编程题]数的划分

热度指数：5007 时间限制：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

输出

算法知识视频讲解

JavaScript

别卷啦！

对于dp[i][j]代表i分为j份。分为以下两类：

每份都没有1：那么只需要将每份都减1然后保证有j份。即加上dp[i-j][j]。

至少有一份1：那么提出1个1,即加上dp[i-1][j-1]。

function divideNumber( n ,  k ) {
    // write code here
    const dp = Array.from(new Array(n+1), ()=>new Array(k+1).fill(0))
    dp[0][0] = 1
    for (let i=1;i<=n;++i){
     for (let j=1;j<=n;++j){
             if ( i-j>=0){
                 dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
             }
     }
 }
  return dp[n][k]        
}

编辑于 2021-01-25 19:03:05 回复(0)