整数划分--DP

红太狼 2022-05-29 10:59 247阅读 0赞

5. [数的划分][Link 1]

问题描述

将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。  
　　例如：n=7，k=3，下面三种分法被认为是相同的。  
1，1，5; 1，5，1; 5，1，1;  
　　问有多少种不同的分法。

输入格式

n，k

输出格式

一个整数，即不同的分法

样例输入

7 3

样例输出

4 \{ 四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;\}

解题思路：

dp\[n\]\[k\]表示把划分为k个数的方案种数；

有俩种情况:

不包含1：

则可以先找出k个1放在每一份中，然后把剩下的n-k分成k份即可，即代码中的  dfs(i-j,j) 部分

包含1：

则先把1拿出来当做单独的一份，则把n-1划分成k-1份即可，即代码中的  dfs(i-1,j-1) 部分

状态转移方程为：

dp\[i\]\[j\]=dp\[i-j\]\[j\]+dp\[i-1\]\[j-1\];        i>j

dp\[i\]\[j\]=1;                                 i=j || j==1

dp\[i\]\[j\]=0;                                 i<j

#include<cstdio>  
    #include<cstdlib>  
    #include<cstring> 
    int dfs(int i,int j){
        if(i==j||j==1)
            return 1;
        else if(i<j)
            return 0;
        else
            return dfs(i-j,j)+dfs(i-1,j-1);    
    }
    int main()   
    {  
        int n,k;  
        scanf("%d %d",&n,&k);  
        int t=dfs(n,k);
        printf("%d\n",t);  
        system("pause");
        return 0;  
    }

一  将n划分为若干个整数的划分数

1.若划分的若干个整数可以相同

设dp\[i\]\[j\]为将i划分为不大于j的划分数

(1) 当i<j时，i不能划分为大于i的数，所以dp\[i\]\[j\]=dp\[i\]\[i\]；

(2) 当i>j时，可以根据划分中是否含有j分为两种情况。

若划分中含有j，划分方案数为dp\[i-j\]\[j\]；

若划分数中不含j，相当于将i划分为不大于j-1的划分数，为dp\[i\]\[j-1\]。

所以当i>j时dp\[i\]\[j\]=dp\[i-j\]\[j\]+dp\[i\]\[j-1\]；

(3) 当i=j时，也分为两种情况：

若划分中含有j只有一种情况，

若划分中不含j相当于将i划分为不大于j-1的划分数。

此时dp\[i\]\[j\]=1+dp\[i\]\[j-1\]。

#include<stdio.h>
    int A(int i,int j){
        if(i==1||j==1) return 1;
        else if(i<j)
            return A(i,i);
        else if(i>j)
            return A(i-j,j)+A(i,j-1);
        else
            return 1+A(i,j-1);
    }
    int main()
    {
    	int s=A(2,2);
    	printf("%d\n",s);
    	return 0;
    }

2.若划分的若干个整数必须不同

设dp\[i\]\[j\]为将i划分为不超过j的不同整数的划分数

(1) 当i<j时，i不能划分为大于i的数，所以dp\[i\]\[j\]=dp\[i\]\[i\]；

(2) 当i>j时，可以根据划分中是否含有j分为两种情况。

若划分中含有j，则其余的划分中最大只能是j-1，方案数为dp\[i-j\]\[j-1\]；

若划分中不含j，相当于将i划分为不大于j-1的划分数，为dp\[i\]\[j-1\]。

所以当i>j时dp\[i\]\[j\]=dp\[i-j\]\[j-1\]+dp\[i\]\[j-1\]；

(3) 当i=j时，两种情况：

若划分中含有j只有一种情况；

若划分中不含j相当于将i划分为不大于j-1的划分数。

此时dp\[i\]\[j\]=1+dp\[i\]\[j-1\]。

[Link 1]: http://blog.csdn.net/buctyyzyn/article/details/43870147