[UVa] 10069 - Distinct Subsequences

題意

求出Z字串在X字串中出現次數，X中的組合可不連續。

解法

類似LCS，假設dp[i][j]為Z的前i個字在X的前j個字的值則可以得到下式。

dp[i][j] = dp[i-1][j] if X[i] != Z[j]
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] if X[i] == Z[j]

注意

大數運算。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		String X , Z ;
		for ( int n = 0 ; n < N ; n ++ ) {
			X = scanner.next();
			Z = scanner.next();
			int length_x = X.length() , length_z = Z.length() ;
			BigInteger[][] dp = new BigInteger[length_x+1][length_z+1] ;
			for ( int i = 0 ; i < length_x + 1 ; i ++ ) {
				dp[i][0] = BigInteger.valueOf(1);
			}
			for ( int i = 1 ; i < length_z + 1 ; i ++ ) {
				dp[0][i] = BigInteger.valueOf(0);
			}
			for ( int i = 1 ; i < length_x + 1 ; i ++ ) {
				for ( int j = 1 ; j < length_z + 1 ; j ++ ) {
					dp[i][j] = dp[i-1][j] ;
					if ( X.charAt(i-1) == Z.charAt(j-1) ) {
						dp[i][j] = dp[i][j].add(dp[i-1][j-1]) ;
					} 
				}
			}
			System.out.println(dp[length_x][length_z]);
		}
	}
}