louisfghbvc的部落格

題目連結:   https://onlinejudge.org/external/109/10943.pdf

題目大意:  問有幾種分法能將n分成k等分，可以重複(比如n=20, k=2 20,0; 0, 20都算一種)

思路:  法1記憶化搜索，直接枚舉並記錄陣列。法2排列組合，可以把k看成隔板，那麼變成n+k-1，取k-1個隔板(相當於隔板排列要不一樣)。

記憶化搜索 代碼1:

int n, k;
int memo[105][105];
const int mod = 1e6;
int dfs(int sum, int c){
    if(sum > n) return 0;
    if(c == k) return sum == n;
    if(memo[sum][c] != -1) return memo[sum][c];
    int res = 0;
    for(int i = 0; i <= n; ++i){
        res += dfs(sum+i, c+1);
        res %= mod;
    }
    return memo[sum][c] = res;
}

int main()
{
    //freopen("out.txt", "w", stdout);
    while(cin >> n >> k, n+k){
        memset(memo, -1, sizeof memo);
        cout << dfs(0, 0) << "\n";
    }
    return 0;
}

排列組合建表 代碼2:  

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long C[205][205];
const int mod = 1e6;
int main()
{
    //freopen("out.txt", "w", stdout);
    C[0][0] = 1;
    for(int N = 1; N <= 201 ; ++N){
        C[N][0] = 1;
        for(int K = 1; K <= N; ++K){
            C[N][K] = (C[N-1][K-1] + C[N-1][K]) % mod;
        }
    }
    while(cin >> n >> k, n+k){
        cout << C[n+k-1][k-1] << "\n";
    }
    return 0;
}