动态规划类型

解题思路:动态规划思想

注意事项:

参考代码:

#include <stdio.h>

#define N 1001

int n, f[N];

int main()

{

    scanf("%d", &n);

    f[1] = 1;  //1的拆分只有1种

    for (int i = 2; i <= n; i++)  //算2~n每个自然数的组合数

    {

        int x = i / 2;   

        for(int j = 1; j <= x; j++)

        //f[i]意思是自然数i在题目规则下一共有多少种情况

        //f[i]可以通过小于等于i/2的自然数的组合数来算，即依赖于小数的组合数，避免重复计算，动态规划思想

        //例如算10的组合数 即算f[10]的值 则f[10]=1(本身)+f[1]+f[2]+f[3]+f[4]+f[5] 

        f[i] += f[j];  

        //自己也算一种情况

        f[i]++;  

    }

    printf("%d", f[n]);

    return 0 ;

}