Java simple DP solution with explanation


  • 0

    In this problem, the valid result are required to be moded by 1000000007. The code have some process to deal with it. Let's let alone this issue in the following discuss and only focus on the principle idea:

    this is a typical DP problem and it is easier to reach the idea by house robber:
    https://leetcode.com/problems/house-robber/#/description

    Back to this problem,we keep six states which are :
    zero: until iteration now, the number of combination(no 'A' in the combination) in which the last attendance is 'P'
    one: until iteration now, the number of combination(no 'A' in the combination) in which the last attendance is 'L'
    two: until iteration now, the number of combination(no 'A' in the combination) in which the last two attendance is 'LL'
    azero: until iteration now, the number of combination( 'A' in the combination) in which the last attendance is 'P' or 'A'
    aone: until iteration now, the number of combination( 'A' in the combination) in which the last attendance is 'L'
    atwo: until iteration now, the number of combination( 'A' in the combination) in which the last two attendance is 'LL'
    We iterate the days from 3 to n, In each step we assume we already know the 6 states of last iteration and initially, we assume two days record are:

    zero: PP, LP -> 2
    one: PL -> 1
    two: LL -> 1
    azero: PA, AP, LA -> 3;
    aone: AL -> 1;
    atwo: 0

    By iteration, we are going to figure out the status of combination in 3 days:
    zero: PPP(zero'), LPP(zero'), PLP(one'), LLP(two') -> 4(zero(last iteration) + one(last iteration) + two(last iteration))
    one: PPL(zero'), LPL(zero') -> 2(zero(last iteration))
    two: PLL(one') -> 1 (one(last iteration))

    azero: PPA, LPA, PLA, LLA, PAP, APP, LAP, ALP -> 8 (zero' + one' + two' + azero' + aone' + atwo')
    aone: PAL, APL, LAL, -> 3(azero')
    atwo: ALL -> 1(atwo')

    So By iteration, we could cumulate the effect of the combination to get the result.

    public class Solution {
        public int checkRecord(int n) {
            if(n == 1){
                return 3;
            }
            if(n == 2){
                return 8;
            }
            
            int zero = 2;
            int one = 1;
            int two = 1;
            int azero = 3; // pa, ap, la 
            int aone = 1;
            int atwo = 0;
            
            for(int i = 3; i <= n; i++){
                int tmpaone = aone;
                int tmpatwo = atwo;
                atwo = aone;
                atwo %= 1000000007;
                aone = azero;
                aone %= 1000000007;
                azero = (int)(((long)zero + one + two + tmpaone + tmpatwo + azero) % 1000000007);
                int tmpone = one;
                int tmptwo = two;
                two = one;
                two %= 1000000007;
                one = zero;
                one %= 1000000007;
                zero =(int)(((long)zero + tmpone + tmptwo) % 1000000007);
                
            }
    
            return (int)(((long)zero + one + two + azero + aone + atwo) % 1000000007);
        }
    }
    

Log in to reply
 

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