TIOJ 1291 N箱M球 ( DP )

1291 - G.N 箱M 球 | TIOJ INFOR Online Judge
dp[ m ][ n ]: m顆球放入 n個箱子，每個箱子至少有一樣東西
這麼一來轉移就很明顯，因為只有球有序所以很好做，轉移要嘛就是丟進一個新的箱子，要嘛就選一個已經有球的箱子，這樣不會有重複計算。一開始我把邊界設成 dp[ i ][ 1 ] = 1，然後試著用一樣的方法轉移結果不對，應該是漏算了什麼，或是枚舉的順序出了問體好複雜。果然這種刷表法的動態規劃方式還是盡量把索引值 0的邊界處理好再乖乖做比較好。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 + 2;
const int MAXM = 200 + 2;
const int MOD = 1e6;

int n, m;

int dp[ MAXM ][ MAXN ];

void solve(){
    memset( dp, 0, sizeof(dp) );
    dp[ 0 ][ 0 ] = 1;
    for(int i = 0; i < MAXM - 1; ++i)
        for(int j = 0; j <= i; ++j){
            ( dp[ i + 1 ][ j ] += dp[ i ][ j ] * j ) %= MOD;
            ( dp[ i + 1 ][ j + 1 ] += dp[ i ][ j ] ) %= MOD;
        }
}

int main(){
    solve();
    while( scanf("%d%d", &n, &m) == 2 && n + m ){
        int ans = 0;
        for(int i = 1; i <= n; ++i)
            ( ans += dp[ m ][ i ] ) %= MOD;
        printf("%d\n", ans);
    }
    return 0;
}