DP——数的计数

Description

要求找出具有下列性质数的个数（包括输入的自然数n): 先输入一个自然数n( n <= 1000),然后对此自然数按照如下方法进行处理： （1）不作任何处理 （2）在它的左边加上一个自然数，但该数不能超过原数的一半 （3）加上数后，继续按此处理，直到不能再加自然数为止

Input

多个测试案例，每个测试案例 输入一个自然数n

Output

输出满足以上条件的所有数的个数

Sample Input

6

Sample Output

6

HINT

对于6，满足条件的数有
6
16
26
126
36
136

大意：还不是很清楚orz

#include<cstdio>
#include<cstring>
using namespace std;

int main()
{
    int n;
    int dp[1100];
    scanf("%d",&n);
    dp[1] = 1;
    for(int i = 2; i <= n ;i++){
        dp[i] = 2;
       for(int j = 2; j <= i/2; j++){
            dp[i] += dp[j];
       }
    }
    printf("%d
",dp[n]);
   return 0;
}