其实DP 的关键在于找到子问题的结构。 
我们规定arr[i][j]为在j左边填写i时的数的个数，很明显： 
arr[i][j]=a[0][i]+a[1][i]+...+arr[i/2][i](i<=j/2) 
我们首先规定 
arr[0][t]=1(0<=t<=n,n为输入的自然数)，因为左边填0时就为本数，数的个数当然为1. 

按照子问题结构，先解子问题，再得到原问题的解。 

 

/* * zy_1009.cpp * *  Created on: 2013年12月15日 *      Author: Administrator */#include 
    
     using namespace std;const int maxn = 1005;int a[maxn][maxn];int n;void prepare(){//	memset(a,0,sizeof(a));	int i,j;	for(i = 0 ; i <= 500 ; ++i){		for(j = 0 ; j <= 1000 ; ++j){			a[i][j] = 0;		}	}	for(i = 1 ; i < maxn ; ++i){		a[0][i] = 1;	}	int k;	for(i = 0 ; i <= n ; ++i){		for(j = 1 ; j <= i/2 ; ++j){			for(k = 0 ; k < j ; ++k){				a[j][i] += a[k][j];			}		}	}}int main(){	while(scanf("%d",&n)!=EOF){		prepare();		int sum = 0;		int i;		for(i = 0 ; i <= n/2 ; ++i){			sum += a[i][n];		}//		printf("%d\n",sum);		cout<
     
      <