/*数字拆解说明：这个题目来自于 数字拆解，我们将之改为C语言的版本，并加上说明。题目是这样的：3 = 2 + 1 = 1 + 1 + 1 所以有三种拆法4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 共七种依此类推，请问一个指定数字NUM的拆解方法个数有多少个？ 解法： 我们以上列中最后一个数字五的拆解为例，假设f(n)为数字n的可拆解方式个数，而f(x, y)为使用y以下的数字来拆解x的方法个数，则观察：5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1使用函数式来表示的话：f(5) = f(4, 1) + f(3, 2) + f(2, 3) + f(1, 4) + f(0, 5)其中f(1, 4) =  f(1, 3) + f(1, 2) + f(1, 1), 但是使用大于1的数字来拆解1没有意义，所以f(1, 4) = f(1, 1), 而同样的，f(0, 5) 会等于f(0，0)，所以：f(5) = f(4, 1) + f(3, 2) + f(2, 3) + f(1, 1) + f(0, 0)依照以上的说明， 使用动态程式规划（Dynamic programming）俩进行求解，其中f(4, 1)其实就是f(5 - 1, min(5 - 1, 1)),f(x, y)就等于f(n - y, min(n - x, y)), 其中n为要拆解的数字， 而min()表示取两者中较小的数。使用一个二维阵列表格table[x][y]来表示f(x, y)，刚开始时， 将每列的索引0与索引1元素值设定为1，因为任何数字以0以下的数拆解必只有1种，而任何数以1以下的数拆解也必只有1种：for(i = 0; i < NUM + 1; i++){    table[i][0] = 1;    table[i][1] = 1;}接下来就开始一个一个进行拆解了，如果数字为NUM，则我们的阵列维度大小必须为NUM * (NUM / 2 + 1)， 以数字10为例，其维为 10 * 6 我们的表格将会如下所示：1 1 0 0 0 01 1 0 0 0 01 1 2 0 0 01 1 2 3 0 01 1 3 4 5 01 1 3 5 6 71 1 4 7 9 01 1 4 8 0 0 1 1 5 0 0 01 1 0 0 0 0 */ #include<stdio.h>#include<stdlib.h>#define NUM 10        //要拆解的数字 #define DEBUG 0int main(void){    int table[NUM][NUM / 2 + 1];        //动态规划表格     int count = 0;    int result = 0;     int i, j, k;        printf("数字拆解\n");    printf("3 = 2 + 1 = 1 + 1 + 1 所以有三种拆法\n");    printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1");    printf("共五种\n");    printf("以此类推，求 %d 有几种拆法 ? ", NUM);            for(i = 0; i < NUM; i++)        //初始化     {        table[i][0] = 1;        table[i][1] = 1;    }        for(i = 2; i <= NUM; i++)        //动态规划     {        for(j = 2; j <= i; j++)        {            if(i + j > NUM)            {                continue;             }             count = 0;             for(k = 1; k <= j; k++)            {                count += table[i - k][(i - k >= k) ? k : i - k];            }            table[i][j] = count;        }    }        for(k = 1; k <= NUM; k++)        //计算并显示结果     {        result += table[NUM - k][(NUM - k >= k) ? k : NUM - k];    }    printf("\n\nresult: %d\n", result);        if(DEBUG)    {        printf("\n除错资讯\n");        for(i = 0; i < NUM; i++)        {            for(j = 0 ; j < NUM / 2 + 1; j++)            {                printf("%2d", table[i][j]);            }            printf("\n");        }    }        return 0;    }