Java solution easy to understand (at least for me)


  • 2
    A
        public int checkRecord(int n) {
        	if (n == 1) {
        		return 3;
        	}
        	if (n == 2) {
        		return 8;
        	}
    
        	long[] dpPLP = new long[n+1]; // awarded count only with P or L, end with P
        	long[] dpPLL = new long[n+1]; // awarded count only with P or L, end with L
        	long[] dpP = new long[n+1]; // awarded count, ends with 'P'
        	long[] dpA = new long[n+1]; // awarded count, ends with 'A'
        	long[] dpL = new long[n+1]; // awarded count, ends with 'L'
        	dpPLP[0] = 0; dpPLL[0] = 0;
        	dpPLP[1] = 1; dpPLL[1] = 1;
        	dpPLP[2] = 2; dpPLL[2] = 2;
        	dpP[0] = 0; dpA[0] = 0; dpL[0] = 0;
        	dpP[1] = 1; dpA[1] = 1; dpL[1] = 1;
        	dpP[2] = 3; dpA[2] = 2; dpL[2] = 3;
    
        	for (int i = 3; i <= n; i++) {
        	        dpPLP[i] = dpPLP[i-1] + dpPLL[i-1];
        	        dpPLL[i] = dpPLP[i-1] + dpPLP[i-2];
        		dpP[i] = dpP[i-1] + dpA[i-1] + dpL[i-1]; // last one is 'P'
        		dpA[i] = dpPLP[i-1] + dpPLL[i-1];
        		dpL[i] = dpP[i-1] + dpA[i-1] + dpP[i-2] + dpA[i-2];
        		dpPLP[i] %= 1000000007;
        		dpPLL[i] %= 1000000007;
        		dpP[i] %= 1000000007;
        		dpA[i] %= 1000000007;
        		dpL[i] %= 1000000007;
        	}
        	return (int)((dpP[n] + dpA[n] + dpL[n]) % (long)1000000007);
        }
    
    

Log in to reply
 

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