整数划分--DP-蒲公英云

整数划分--DP

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

数的划分

问题描述

　　将整数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\]。