【蓝桥杯】ADV-153 数的划分

正文索引 [隐藏]

题目描述:

一个正整数可以划分为多个正整数的和,比如n=3时:
3;1+2;1+1+1;
共有三种划分方法。
给出一个正整数,问有多少种划分方法。
数据规模和约定:
n <= 100

输入描述:

一个正整数n。

输出描述:

一个正整数,表示划分方案数。

输入样例:

3

输出样例:

3

解题思路:

我们想要知道n的方案数就必须知道n-i的方案数,而n-i的方案数是多少呢?n-i可以取0~(n-i)个数,…,最后n=0时,只能取到一个数0,此时方案数为1。dp[i][j]表示数字 i 可以被拆分成不超过 j 的方案数,初始化dp[0][i]为1。当i>=j时有状态转移方程为:dp[i][j] = dp[i][j-1] + dp[i-j][j],当j>i时我们也只能取dp[i][i],因为i不可能被拆分成超过i的方案数。最后输出dp[n][n]即可知道数字n的拆分方案数。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int N = 105;

int dp[N][N];   //dp[i][j]表示把i拆分成不超过j的方案数

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    ms(dp,0);
    Up(i,0,n)
    {
        dp[0][i] = 1;
    }
    Up(i,1,n)
    {
        Up(j,1,n)
        {
            //dp[i][j]只有包含j和不包含j两种情况
            if(i >= j)
            {
                dp[i][j] = dp[i][j-1] + dp[i-j][j];
            }
            else dp[i][j] = dp[i][i];
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}