t0ur1st

题目描述：

输入描述：

一个正整数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;
}