[C/C++ 演算法]- 數字拆解 – jashliao部落格

#include 
#include 
#define NUM 10    //  要拆解的數字
#define DEBUG 0

void init(int[][NUM / 2 + 1]);
int min(int, int);
int f(int[][NUM / 2 + 1], int, int);
void dp(int[][NUM / 2 + 1]);
int count(int[][NUM / 2 + 1]);
void print(int[][NUM / 2 + 1]);
int main(void) {
int table[NUM][NUM / 2 + 1] = {0};
init(table);
dp(table);
printf("可拆解出 %d 組數字\n", count(table));
if(DEBUG) { print(table); }
return 0;
}
void init(int table[][NUM / 2 + 1]) {
int i;
for(i = 0; i < NUM; i++) {
table[i][0] = 1;  // 任何數用 0 以下的數拆解必只有 1 種
        table[i][1] = 1;  // 任何數用 1 以下的數拆解必只有 1 種
    }
}
int min(int a, int b) { return a > b ? b : a; }
int f(int table[][NUM / 2 + 1], int x, int y) {
int c, i;
for(c = 0, i = 1 ; i <= y; i++) { c += table[x - i][min(x - i, i)]; }
return c;
}
void dp(int table[][NUM / 2 + 1]) {
int x;
for(x = 2; x < NUM; x++){
int y;
for(y = 2; y < NUM / 2 + 1 && y <= x; y++) if(x + y <= NUM) {
table[x][y] = f(table, x, y);
}
}
}
int count(int table[][NUM / 2 + 1]) {
int i, result;
for(i = 1, result = 0 ; i <= NUM; i++) {
result += table[NUM - i][(NUM - i >= i) ? i : NUM - i];
}
return result;
}
void print(int table[][NUM / 2 + 1]) {
int i;
for(i = 0; i < NUM; i++) {
int j;
for(j = 0; j < NUM/2+1; j++) {
printf("-", table[i][j]);
}
printf("\n");
}
}