CFR 653 B. Bear and Compressing ( DP )

Problem - 653B - Codeforces
題意：
給字串初始的長度，和若干組操作。操作用兩個字串描述，第一個是兩個字母，第二個是一個字母，代表若且唯若當前準備要進行操作的字串前兩個字母和指定操作的字串一致，就可以將該字串轉換成指定操作的第二個字串( 字母 )。最終的字母是 'a'，求有多少種不同的原始字串滿足條件。
解法：
反過來想，透過給定的操作，'a'最終可以到達幾種長度為某的字串？
dp[ i ][ j ] : 由'a'出發，到達長度為 i 的字串，開頭為 'a' + j，此狀態的方案數。

int N, Q;
vs A, B;

void init(){
    cin >> N >> Q;
    A = B = vs( Q );
    for( int i = 0; i < Q; ++i )
        cin >> A[ i ] >> B[ i ];
}

vvi dp;

void preprocess(){
    dp = vvi( N + 1, vi( 26 ) );
    dp[ 1 ][ 0 ] = 1;
    for( int i = 1; i < N; ++i )
        for( int j = 0; j < 26; ++j )
            if( dp[ i ][ j ] ){
                for( int k = 0; k < Q; ++k )
                    if( B[ k ][ 0 ] - 'a' == j )
                        dp[ i + 1 ][ A[ k ][ 0 ] - 'a' ] += dp[ i ][ j ];
            }
}

void solve(){
    int ans = 0;
    for( int i = 0; i < 26; ++i )
        ans += dp[ N ][ i ];
    cout << ans << endl;
}