整数的划分 动态规划

题目描述

每个非负整数都可以被拆分，比如说

2 = 2
2 = 1+1

3 = 3
3 = 2+1
3 = 1+1+1

输入格式
一个非负整数$n(0 \leq n \leq 100)$

输出格式
输出可以被拆分的方案数

输入样例

4

输出样例

5

样例解释

4 = 4
4 = 3+1
4 = 2+2
4 = 2+1+1
4 = 1+1+1+1
共5种

本题是我在学 $dp$ 时候做的一道题

看到题目首先来一发暴力搜索

---

40分解法

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n,ans;
int vis[500005];
void dfs(R int x,R int y)
{
    if(x<0)return;//拆过头了
    if(!x)//没法拆了
    {
        ++ans;
        return;
    }
    for(R int i=vis[y-1]; i<=x; i++)//要比上次拆的大
    {
    	//这种拆法是反过来拆的，本质上一样
    	//每一个拆分出的数字都记录在vis数组中
    	//例如 4 = 1+1+2
        if(i<n)
        {
            vis[y]=i;
            dfs(x-i,y+1);
        }
    }
}
signed main()
{
    scanf("%lld",&n);
    if(!n)return puts("1"),0;//0就一种
    vis[0]=1;//最小拆个1出来
    dfs(n,1);
    printf("%lld\n",ans+1);//不拆也是一种
    return 0;
}

如果认为暴力能过，那请看以下数据

输入: 100
输出: 190569292

综上所述，这道题正解是$dp$

---

100分 解法一

设 $dp[i][j]$ 表示 $i$ 拆分成 $j$ 个数的方案数

我们可以把 $j$ 看作 $j$ 个桶，$i$ 就是 $i$ 个$1$

1.$dp[i-1][j-1]$
一个桶里已经放了一个 $1$ 了，还有 $i-1$ 个 $1$ 要划分到 $j-1$ 个桶考虑$i-1$的$j-1$划分（$1$本身作为一个划分）保证划分中包含$1$

1. $dp[i-j][j]$
   先在每一个桶里都放个 $1$，还有 $i-j$ 个 $1$ 要划分到这 $j$ 个桶里（$i-j$不作为单独作为划分，因此还是划分为$j$组），考虑 $i-j$ 的 $j$ 划分，在合法的情况下保证划分中不包含$1$
   $[$ 对于 $i$ 的 $j$ 划分$a_k$（ $\sum\limits_{k=1}^{j}{a_k}=i,a_k\in \mathbb{Z}_+$ ），都有 $a_k>0$ ，因此 $a_k-1$ 对应了 $i-j$ 的 $j$ 划分 $]$

所以状态转移方程就是

$dp[i][j]=dp[i-j][j]+dp[i-1][j-1]$

注：对于当前状态的划分中包含 $1$ （$dp[i-1][j-1]$），不保证状态转移后仍有 $1$

例如 $dp[7][3]$ 的一种划分方式 $1+2+4$

$dp[7][3]$ $\xrightarrow{}$ $1+dp[6][2]$ $\xrightarrow{}$ $1+\frac{dp[4][2]}{+1}$ $\xrightarrow{}$ $1+\frac{1+dp[3][1]}{+1}$ $\xrightarrow{}$ $1+\frac{1}{+1}+\frac{3}{+1}$ $\xrightarrow{}$ $1+2+4$

边界:

1. $0$ 的总方案数为 $1$

2. $j=1$ ，方案数就是 $1$

3. $i<j$ 时无法划分成 $j$ 个数，方案数为 $0$

4. $i=j$ 时方案数为 $1$

最后答案就是 $\sum\limits_{i=1}^{n}{dp[n][i]}$

时间复杂度 $O(n^2)$

空间复杂度 $O(n^2)$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n,ans;
int dp[105][105];
signed main()
{
    scanf("%lld",&n);
    if(!n)return printf("1\n"),0;
    for(R int i=1; i<=n; i++)
        for(R int j=1; j<=n; j++)
            if(i==j||j==1)dp[i][j]=1;
            else if(i>j) dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
    for(R int i=1; i<=n; i++)
        ans+=dp[n][i];
    printf("%lld\n",ans);
    return 0;
}

---

100分 解法二

设 $dp[j]$ 为 $j$ 的所有划分方案数

对于 $\forall j \in \mathbb{Z}_+$，$dp[j]=\sum\limits_{i=1}^{j}{dp[j-i]}$

边界: $0$ 的方案数为 $1$

时间复杂度 $O(n^2)$

空间复杂度 $O(n)$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n,dp[105]={1};
signed main()
{
    scanf("%lld",&n);
    for(R int i=1; i<=n; i++)
        for(R int j=i; j<=n; j++)
            dp[j]+=dp[j-i];
    printf("%lld\n",dp[n]);
    return 0;
}