题意整理
- 给定一个整数n和一个整数k,将n分成k份。
- 每份不能为空,问有多少种分法(组合相同,排列不同的算同一种分法)。
方法一(暴力递归)
1.解题思路
- 递归终止条件:已经分了k份。
- 递归如何推进:份数加一,剩余的数字rest要减去已经分配的,而use是当前尝试分配的(只要小于rest,都可以尝试)。
2.代码实现
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 被划分的数 * @param k int 化成k份 * @return int */ //k表示总划分份数,cnt记录几种分法 int k; int cnt; int mod=1000000007; public int divideNumber (int n, int k) { // 初始化k和cnt this.k=k; this.cnt=0; //开始递归 dfs(0,n,1); return cnt; } private void dfs(int depth,int rest,int use){ //如果达到k份,递归终止 if(depth==k){ //如果此时刚好剩余为0,记录的分法加一 if(rest==0){ cnt=(cnt+1)%mod; } return; } //如果能继续划分,份数加一,rest减去已经分配的,use是每一次尝试划分多少 for(int i=use;i<=rest;i++){ dfs(depth+1,rest-i,i); } } }
3.复杂度分析
- 时间复杂度:假设不算重复的情况,把数字n分成k份,相当于在n-1个空中,插入k-1个分隔符,总共有 种方案,所以时间复杂度是 。
- 空间复杂度:需要额外深度为k的递归栈,所以空间复杂度为 。
方法二(动态规划)
1.解题思路
- 状态定义: 表示数字i分为j份总共有多少种分法。
- 状态初始化:数字0划分为0份总共有1种分法,所以 为1。
- 状态转移:根据每份不能为空,我们可以将划分的情况分为两种,一种是至少有一份分配了数字1,另外一种是,所有的份数都没有分配数字1(如果没有分配数字1,必然分配了大于1的数字)。于是,如果至少分配了一份是数字1,那么剩下的分法就是 ,即将数字i-1分为j-1份;如果没有分配数字1,那么我们一定可以给j份都提前放一个数字1,剩下的就是 ,即将数字i-j分为j份。所以状态转移方程是: 。
动图展示:
2.代码实现
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int 被划分的数 * @param k int 化成k份 * @return int */ public int divideNumber (int n, int k) { // 初始化dp数组,赋初值 int[][] dp=new int[n+1][k+1]; dp[0][0]=1; int mod=1000000007; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ //由于每份不能为空,所以划分数肯定大于总份数 if(i>=j){ //分为至少存在一份是1,和所有份数大于1两种情况 dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%mod; } } } return dp[n][k]; } }
3.复杂度分析
- 时间复杂度:总共两层循环,最多遍历 次,所以时间复杂度是 。
- 空间复杂度:需要额外大小为的dp数组,所以空间复杂度为 。