[UVa] 10069 - Distinct Subsequence

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10069 - Distinct Subsequences
Source            : UVA Online Judge
Category          : Dynamic Programing, Big Integer
Algorithm         : Dynamic Programing
Verdict           : Accepted

import java.io.IOException;  
import java.io.InputStream;  
import java.io.PrintWriter;  
import java.math.BigInteger;  
import java.util.Arrays;  
import java.util.Scanner;  
import java.util.*;  
  
/** 
 * 
 * @author Dipu 
 */  
class Main {  
  
    /** 
     * @param args the command line arguments 
     */  
      
    static BigInteger dp[][];  
    static Boolean memoize[][];  
    static String x, z;  
    static int lenx, lenz;  
          
    public static void main(String args[]) {  
        FastReader in = new FastReader(System.in);  
        PrintWriter pw = new PrintWriter(System.out); 
        dp = new BigInteger[10005][105];  
        memoize = new Boolean[10005][105];  
        int tc = in.nextInt();  
        for (int tcase = 1; tcase <= tc; tcase++) {  
            x = in.next();  
            z = in.next();  
            lenx = x.length();  
            lenz = z.length();  
            for (Boolean[] row : memoize) {  
                Arrays.fill(row, false);  
            }  
            BigInteger ans = solve(0, 0);  
            pw.println(ans);  
        }  
        pw.close();  
    }  
    public static BigInteger solve(int i, int j) {  
        if (j >= lenz) return BigInteger.ONE;  
        if (i >= lenx) return BigInteger.ZERO;  
        if (memoize[i][j] == true) return dp[i][j];  
        memoize[i][j] = true;  
        BigInteger sum = BigInteger.ZERO;  
        if (x.charAt(i) != z.charAt(j)) sum = solve(i+1, j);  
        else sum = solve(i+1, j+1).add(solve(i+1, j));  
        return dp[i][j] = sum;  
    }  
      
    static void debug(Object...obj) {  
        System.err.println(Arrays.deepToString(obj));  
    }  
  
    static class FastReader {  
        InputStream is;  
        private byte[] inbuf = new byte[1024];  
        private int lenbuf = 0, ptrbuf = 0;  
  
        public FastReader(InputStream is) {  
            this.is = is;  
        }  
  
        public int readByte() {  
            if (lenbuf == -1) throw new InputMismatchException();  
            if (ptrbuf >= lenbuf) {  
                ptrbuf = 0;  
                try {  
                    lenbuf = is.read(inbuf);  
                } catch (IOException e) {  
                    throw new InputMismatchException();  
                }  
                if (lenbuf <= 0) return -1;  
            }  
            return inbuf[ptrbuf++];  
        }  
  
        public boolean isSpaceChar(int c) {  
            return !(c >= 33 && c <= 126);  
        }  
        private boolean isEndOfLine(int c) {  
            return c == '\n' || c == '\r' || c == -1;  
        }  
  
        public int skip() {  
            int b;  
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;  
            return b;  
        }  
  
        public String next() {  
            int b = skip();  
            StringBuilder sb = new StringBuilder();  
            while (!(isSpaceChar(b))) {  
                sb.appendCodePoint(b);  
                b = readByte();  
            }  
            return sb.toString();  
        }  
  
  
  
        public String nextLine() {  
            int c = skip();  
            StringBuilder sb = new StringBuilder();  
            while (!isEndOfLine(c)){  
                sb.appendCodePoint(c);  
                c = readByte();  
            }  
            return sb.toString();  
        }  
  
        public int nextInt() {  
            int num = 0, b;  
            boolean minus = false;  
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;  
            if (b == '-') {  
                minus = true;  
                b = readByte();  
            }  
            while (true) {  
                if (b >= '0' && b <= '9') {  
                    num = (num << 3) + (num << 1) + (b - '0');  
                } else {  
                    return minus ? -num : num;  
                }  
                b = readByte();  
            }  
        }  
  
        public long nextLong() {  
            long num = 0;  
            int b;  
            boolean minus = false;  
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;  
            if (b == '-') {  
                minus = true;  
                b = readByte();  
            }  
  
            while (true) {  
                if (b >= '0' && b <= '9') {  
                    num = (num << 3) + (num << 1) + (b - '0');  
                } else {  
                    return minus ? -num : num;  
                }  
                b = readByte();  
            }  
        }  
  
        public double nextDouble() {  
            return Double.parseDouble(next());  
        }  
  
        public char[] next(int n) {  
            char[] buf = new char[n];  
            int b = skip(), p = 0;  
            while (p < n && !(isSpaceChar(b))) {  
                buf[p++] = (char) b;  
                b = readByte();  
            }  
            return n == p ? buf : Arrays.copyOf(buf, p);  
        }  
  
        public char readChar() {  
            return (char) skip();  
        }  
    }  
}