Java 4 lines DP solution with state transition table explained


  • 2
    Y

    Let AnLn denote number of strings containing n A's and ending with n L's
    For example:

    When n = 1 we have:

    	 A0L0: P
    	 A0L1: L
    	 A0L2:
    	 A1L0: A
    	 A1L1:
    	 A1L2:
    	 Done:
    

    When n = 2 we have:

    	 A0L0: LP, PP
    	 A0L1: PL
    	 A0L2: LL
    	 A1L0: AP, LA, PA
    	 A1L1: AL
    	 A1L2:
    	 Done: AA
    	
    

    In general we have this transition table:

    	 -----+---------------
    	 INIT | A -- L -- P --
    	 -----+---------------
    	 A0L0 | A1L0 A0L1 A0L0
    	 A0L1 | A1L0 A0L2 A0L0
    	 A0L2 | A1L0 Done A0L0
    	 A1L0 | Done A1L1 A1L0
    	 A1L1 | Done A1L2 A1L0
    	 A1L2 | Done Done A1L0
    

    From the transition table we see that:
    A0L0 of n can result from A0L0 + A0L1 + A0L2 of n - 1 by appending P
    A0L1 of n can only result from A0L0 of n - 1 by appending L
    and so on...

    That's why in each iteration we update:
    dp[0] = dp[0] + dp[1] + dp[2]
    dp[1] = dp[0]
    and so on...

    public int checkRecord(int n) {
        int[] dp = { 1, 1, 0, 1, 0, 0 }; // init table for n = 1
        for (int i = 2; i <= n; i++) // updating table for n = i
            dp = new int[] { sum(dp, 0, 2), dp[0], dp[1], sum(dp, 0, 5), dp[3], dp[4] };
        return sum(dp, 0, 5);       
    }                                   
    
    static int sum(int[] arr, int l, int h) {
        int s = 0;  
        for (int i = l; i <= h; i++) 
            s = (s + arr[i]) % 1000000007;  
        return s;                   
    } 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.