UVa 10069 : Distinct Subsequences

UVa演習 : 2014/6/10 (火) 問７

問題リンク : http://uva.onlinejudge.org/external/100/10069.html

問題概要：
２つの文字列X,Zがあたえられる
X中に部分列としていくつZが存在するか？数えよ

解法:
動的計画法
dp[Z[0:i]][X[0:j]] := 総和
ただし答えは10^100を越える場合がある
JavaのBigInteger推奨

Sampleの2番について考える
実際のDP配列は以下のようになる

　 "rabbbit
 " 11111111
 r 01111111
 a 00111111
 b 00012333
 b 00001333
 i 00000033
 t 00000003

'"'は空文字を表す
"rabbbit中の各場所で空文字は唯一１つだけつくれるとする
Xを0から見ていき、Z[i]とX[j]が同じアルファベットの場合、
dp[i][j-1]とdp[i-1][j-1]がdp[i][j]の値となる
dp[i][j-1]は、j-1まででZ[0:i]をつくる数の総和で
dp[i-1][j-1]はj-1まででZ[0:i-1]を作る総和 ( Z[0:i-1]に今みてるアルファベットを加える)
そうでない場合、dp[i][j-1]がdp[i][j]の値となる

コード :

import java.io.*;
import java.math.*;
import java.util.*;

class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        while( T-- > 0 ){
            String X = in.readLine();
            String Z = in.readLine();
            int xlen = X.length(), zlen = Z.length();
            BigInteger[][] dp = new BigInteger[zlen+1][xlen+1];
            for(int i=0;i<=zlen;i++) dp[i][0] = BigInteger.ZERO;
            for(int i=0;i<=xlen;i++) dp[0][i] = BigInteger.ONE;
            for(int i=1;i<=zlen;i++){
                for(int j=1;j<=xlen;j++){
                    dp[i][j] = dp[i][j-1];
                    if( X.charAt(j-1) == Z.charAt(i-1) ) dp[i][j] = dp[i][j].add(dp[i-1][j-1]);
                }
            }
            System.out.println(dp[zlen][xlen]);
        }
    }
}