题干：

One curious child has a set of N little bricks. From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick. Picture gives examples of staircase for N=11 and N=5:

Your task is to write a program that reads from input numbers N and writes to output numbers Q - amount of different staircases that can be built from exactly N bricks.

Input

Numbers N, one on each line. You can assume N is between 3 and 500, both inclusive. A number 0 indicates the end of input.

Output

Numbers Q, one on each line.

Sample Input
3 
5 
0 

Sample Output
1
2

解题报告：

   考虑动态规划。因为具有重叠子问题和无后效性，考虑dp[i][j]代表用i块砖块建出最大高度为j的图形。因为题目的限制，发现最大高度一定是最后一列，转移就是枚举前一列的最大高度。因为数据范围比较小，所以n^3的算法足够用，如果n再大一些，考虑前缀和优化一下，或者状态的定义改变一下，改成最后一列高度小于等于j的。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 500 + 5;
ll dp[MAX][MAX];
int low[MAX];
int main()
{
	for(int i = 1; i<=500; i++) dp[i][i]=1;
	dp[3][2]=1;
	for(int i = 4; i<=500; i++) {
		for(int j = 1; j<=i-1; j++) {
			for(int k = 1; k<=j-1; k++) {
				if(i-j>0) dp[i][j] += dp[i-j][k];
			}
		}
	}
	int n;
	while(scanf("%d",&n) && n) {
		ll sum = 0;
		for(int i = 1; i<=n-1; i++) sum += dp[n][i];
		printf("%lld\n",sum);
	}
	return 0 ;
}

代码2：

for(int i=0; i<=n; i++) dp[0][i]=1;

for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++)
		if(i>=j)
			dp[i][j]=dp[i-j][j-1]+dp[i][j-1];
		else
			dp[i][j]=dp[i][j-1];