整数区分--古い成長談の問題動態計画

テキストリンク:http://www.cnblogs.com/xiaoxian1369/archive/2011/09/12/2174212.html
1)练习组み合わせ数学能力.2)练习再帰思想3)练习DPはとにかく経典のもう経典のテーマである:この良い问题は:1.nをいくつかの正の整数の和の区分数に分ける.2.nをk個の正の整数の和に分割する分割数.3.nを最大数kを超えない分割数に分割する.4.nをいくつかの奇正整数の和に分割する分割数.5.nをいくつかの異なる整数の和に分割する分割数.
 
1.nをm以下に分割する分割法: 
 1).複数の整数を分割する場合は、次のようになります.
 　　 dp[n][m]= dp[n][m-1]+ dp[n-m][m]  dp[n][m]は整数nの分割のうち、各数がmより大きくない分割数を表す.     分割数は、次の2つのケースに分けられます.     a.区分における各数はmよりも小さい、各数がm-1よりも大きくないことに相当するため、分割数はdp[n][m-1]となる.    　　 b.区分のうち1つの数がmであればnからmを減算し、残りはn-mを区分することに相当するため、分割数はdp[n-m][m]である.
2).複数の異なる整数を分割する場合:
　　dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]   dp[n][m]は整数nの分割のうち、各数がmより大きくない分割数を表す.   　　 同じように状況を分けて2つの状況に分けます.    a.区分の各数はmより小さく、各数がm-1より大きくないことに相当し、区分数はdp[n][m-1]である.    b.区分のうちの1つの数はm.nからmを減算し、残りはn-mを相当に区分する、
そして各数はm−1以下であるため、スコアはdp[n−m][m−1]となる
2.nをk個の数に分割する分割法:
　dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
   メソッドは、次の2つに分類できます.   第1類:n部の中で1の分法を含まないで、1部ごとにすべて>=2を保証するため、先にk個の1分を出すことができます   各部に着いて、それから残りのn-kをk部に分けるといいです.分法はdp[n-k][k]です.  第二類:n部のうち少なくとも1部が1の分法があり、まず1部を単独の1部として出すことができ、残り   下のn-1をさらにk-1部に分けるとよいが,分法はdp[n-1][k-1]
　　
3.nをいくつかの奇数に分割する分割法:(分からない)
g[i][j]:iをj個の偶数に分割する
f[i][j]:iをj個の奇数に分割する   g[i][j] = f[i - j][j];    　　f[i][j] = f[i - 1][j - 1] + g[i - j][j];
 
通りすがりの大牛は説明を求めて、ありがとうございます~
コードは次のとおりです.

/*
 * hit1402.c
 *
 *  Created on: 2011-10-11
 *      Author: bjfuwangzhu
 */

#include
#include
#define nmax 51
int num[nmax][nmax]; // i      j   
int num1[nmax][nmax]; // i      j     
int num2[nmax][nmax]; // i   j  
int f[nmax][nmax]; // i   j   
int g[nmax][nmax]; // i   j   
void init() {
    int i, j;
    for (i = 0; i < nmax; i++) {
        num[i][0] = 0, num[0][i] = 0, num1[i][0] = 0, num1[0][i] = 0, num2[i][0] =
                0, num2[0][i] = 0;
    }
    for (i = 1; i < nmax; i++) {
        for (j = 1; j < nmax; j++) {
            if (i < j) {
                num[i][j] = num[i][i];
                num1[i][j] = num1[i][i];
                num2[i][j] = 0;
            } else if (i == j) {
                num[i][j] = num[i][j - 1] + 1;
                num1[i][j] = num1[i][j - 1] + 1;
                num2[i][j] = 1;

            } else {
                num[i][j] = num[i][j - 1] + num[i - j][j];
                num1[i][j] = num1[i][j - 1] + num1[i - j][j - 1];
                num2[i][j] = num2[i - 1][j - 1] + num2[i - j][j];
            }
        }
    }
    f[0][0] = 1, g[0][0] = 1;
    for (i = 1; i < nmax; i++) {
        for (j = 1; j <= i; j++) {
            g[i][j] = f[i - j][j];
            f[i][j] = f[i - 1][j - 1] + g[i - j][j];
        }
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int n, k, i, res0, res1, res2, res3, res4;
    init();
    while (~scanf("%d %d", &n, &k)) {
        res0 = num[n][n];
        res1 = num2[n][k];
        res2 = num[n][k];
        for (i = 0, res3 = 0; i <= n; i++) {
            res3 += f[n][i];
        }
        res4 = num1[n][n];
        printf("%d
%d
%d
%d
%d

", res0, res1, res2, res3, res4);
    }
    return 0;
}

正の整数を連続する正の整数の和に分割15は4種類の連続する整数の加算の形式に分割することができる:15 7 8 4 5 6 1 3 4    まず一般的な形式を考慮し、nを分割された正の整数とし、xを分割後最小の整数とし、nに分割がある場合、結果はxであり、2つの分割がある場合、xとx+x+1であり、mの分割がある場合、x、x+x+1 x+2、...、x+1 x+2...x+m-1は各結果を加算して1つの式(i*x+i*(i-1)/2)を得る=n,iは現在の分割後に加算される正の整数の個数である.条件を満たす区分は,xを正の整数にするすべての場合である.上記の例のように、i=1の場合、すなわち正の整数に分割される場合、x=15、i=2の場合、x=7である.x=3の場合、x=4、x=4の場合、4/9、正の整数ではないので、15を4つの正の整数に分割して加算することはできません.x=5の場合、x=1になります.    ここでもう一つ質問がありますが、このiの最大値はいくらですか?しかし、nより小さいに違いない.nは、前例の1 2 3 4 5のような最小値1の区分に分解できると仮定することができる.これはnの最大数の区分である.この仮定を満たさなければ,iはこの区分の正の整数個数よりも小さいに違いない.従って、i*(i+1)/2<=nの式が得られ、すなわち、iがこの式を満たすとnが分割される可能性がある.
コードは次のとおりです.

void split(int n) {
    int i, j, te, x, xlen;
    for (i = 1, xlen = 0; (te = i * (i - 1) / 2) < n; i++) {
        x = n - te;
        if (x % i == 0) {
            x /= i;
            printf("%d", x);
            for (j = 1; j < i; j++) {
                printf("%d ", x + j);
            }
            printf("
");
            xlen++;
        }
    }
    printf("%d
", xlen);
}

以下のリンクは筆者自身が与えたもので、整数分割のもう一つの方法である母関数法について話しています.ブログで与えられたテーマリンクには整数分割があり、テンプレート化されたテーマでもあります.そして、この母関数に対する説明ブログもよく書かれていて、みんなが学ぶ価値があります.
リンク:http://www.wutianqi.com/?p=596