题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1531
Time limit: 3.000 seconds

Problem Description

Little Pippy has got again a big bunch of boxes of chocolates on her 7-th birthday. Her parents are anxious about the health of her teeth, so they have allowed her to take only a limited number of chocolates; lets call this number N. They know that Pippy always shares her belongings with her friends, so they have fixed a sufficiently large number to make sure that all are happy. The chocolates are packed in several types of boxes. Each type of box contains a certain number of chocolates which is written above the box. Boxes of different types contain different numbers of chocolates. If a box contains k chocolate(s) we will call it type-k box. Now Pippy should take exactly N chocolates without tearing apart any box. Your job is to determine in how many ways Pippy can do this. You may assume that there are infinitely many boxes of each type from type-1 to type-N.

For example, lets assume that Pippy has been asked to take 3 chocolates. She can take only one
type-3 box or she can take one type-2 box and one type-1 box or she can take 3 type-1 boxes.

Input

There will be several lines as input each containing a candidate N as described above. N can be any nonnegative number less than or equal to 5000. It may look like that N is very big for a little 7 year old girl; but remember she has lots of friends. And, who knows, may be you are one of her friends!

Output

For each N, print an integer on a single line indicating the number of ways Pippy can take N chocolates.

Sample Input

3
4
5

Sample Output

3
5
7

Problem solving report:

Description: 整数划分问题，给一个整数，问其有多少种组合方式。
Problem solving: 用dp[i][j]表示将i拆成若干个数字，最大的那个数字不超过j的方案数。
则dp[i][j] = dp[i][j-1]+dp[i-j][j]；
数i的拆分数不超过j的方案数=不划分出j时数i拆分数不超过j-1的组合数+划分出一个j后数i-j拆分数不超过j的组合数。
考虑到状态转移方程j只与j、j-1有关，故可转化为一维的dp[i]=dp[i]+dp[i-j];

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 105;
const int MAXN = 5005;
struct Large {
    int len;
    int num[MAXM];
    Large() {
        len = 1;
        memset(num, 0, sizeof(num));
    }
}dp[MAXN];
Large Add(Large a, Large b) {
    Large c;
    int t = 0;
    c.len = max(a.len, b.len);
    for (int i = 0; i < c.len; i++) {
        c.num[i] = a.num[i] + b.num[i] + t;
        t = c.num[i] / 10;
        c.num[i] %= 10;
    }
    while (t) {
        c.num[c.len++] = t % 10;
        t /= 10;
    }
    return c;
}
int main() {
    int n;
    dp[0].num[0] = 1;
    for (int i = 1; i < MAXN; i++)
        for (int j = i; j < MAXN; j++)
            dp[j] = Add(dp[j], dp[j - i]);
    while (~scanf("%d", &n)) {
        for (int i = dp[n].len - 1; ~i; i--)
            printf("%d", dp[n].num[i]);
        printf("\n");
    }
    return 0;
}
/* 
 * @Author: lzyws739307453 
 * @Language: Java 
 */
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int MAX = 5005;
        Scanner cin = new Scanner(System.in);
        BigInteger [] dp = new BigInteger[MAX];
        dp[0] = BigInteger.ONE;
        for (int i = 1; i < MAX; i++)
            dp[i] = BigInteger.ZERO;
        for (int i = 1; i < MAX; i++)
            for (int j = i; j < MAX; j++)
                dp[j] = dp[j].add(dp[j - i]);
        int n;
        while (cin.hasNextInt()) {
            n = cin.nextInt();
            System.out.println(dp[n]);
        }
    }
}