整数求和

#include <stdio.h>

int main(int argc, const char * argv[]){
    int a[120][120];
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 初始化
    for(int i=1; i<=n; i++){
        a[i][0] = 0;
        a[0][i] = 0;
        a[i][1] = 1;
        if(i==1){
            a[1][i] = 1;
        }else{
            a[1][i] = 0;
        }
    }
    
    // 进行计算
    for(int i=2; i<=n; i++){
        for(int j=2; j<=m; j++){
            if(i>=j){
                // [1,j,i]
                // 分解 [j-1, j] + [j][j] + [j+1][j]
                // 1~j-1，可以成为组合的加数，即用1到j-1表示j，=> a[j-1][j]
                // j, 可以成为组合的加数，即刚好单个加数{j}表示j, => 1
                // j+1~j, 由于这些数都大于j,不可能成为加数 => 0
                a[i][j] = a[j-1][j] + 1;
            }else{
                // [1,i,j]
                // 分解 [i-1][j] + [i-1][j-i]
                // 加数中无i，从1~i-1中挑选几个数的和等于j => a[i-1][j]
                // 加数中有i，从1~i-1中挑选几个数的和加上i等于j，相当于，从1~i-1中挑选几个数的和等于 j-i => a[i-1][j-i]
                a[i][j] = a[i-1][j] + a[i-1][j-i];
            }
        }
    }
    printf("%d", a[n][m]);
    return 0;
}