整数的划分 动态规划

题目描述

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

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\)

2. \(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;
}