1009. 整数的拆分

int n;
while(cin>>n) cout<<ans[n][n]<<endl;

//状态 dp[i][j]表示以j为最大值分解i的最多个数
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 105;
int dp[maxn][maxn];

int main() {
    fill(dp[0], dp[0] + maxn * maxn, 0);
    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            if (i == 1 || j == 1) {
                dp[i][j] = 1;
            }
        }
    }
    for (int i = 1; i < maxn; ++i) {
        for (int j = 1; j < maxn; ++j) {
            if (j > i) {
                dp[i][j] = dp[i][j - 1];
            }
            else if (i == j) {
                dp[i][j] = dp[i][j - 1] + 1;
            }
            else {
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
            }
        }
    }
    int n;
    while (cin >> n) {
        cout << dp[n][n] << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int a[1001];
bool vis[30];
int n,ans;

void dfs(int num,int cnt)   //cnt当前拆分中的数量+1。 
{
    if(num == 0) {      //拆分完毕 
        ans++;
        return;
    }
    for(int i = 1; i <= num; i++) {     //搜索进行拆分，拆分的一定要大于等于前一个数 
        if(i >= a[cnt-1]) {     //关键在这里 
            a[cnt] = i;
            num-=i;
            dfs(num,cnt+1);
            num+=i;     //回溯 
        }
    }
}

int main()
{
    while(cin>>n) {
        ans = 0;
        dfs(n,1);       //从1开始搜索方便第一个元素的搜索判断 
        cout<<ans<<endl;
    }
    return 0;
}