LeetCode 552 - Student Attendance Record II


Related: LeetCode 551 - Student Attendance Record I
https://leetcode.com/problems/student-attendance-record-ii
Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.
A student attendance record is a string that only contains the following three characters:
  1. 'A' : Absent.
  2. 'L' : Late.
  3. 'P' : Present.
A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
Example 1:
Input: n = 2
Output: 8 
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times.
Note: The value of n won't exceed 100,000.
X.
定义了三个DP数组P, L, A，其中P[i]表示数组[0,i]范围内以P结尾的所有排列方式，L[i]表示数组[0,i]范围内以L结尾的所有排列方式，A[i]表示数组[0,i]范围内以A结尾的所有排列方式。那么最终我们所求的就是P[n-1] + L[n-1] + A[n-1]了。那么难点就是分别求出P, L, A数组的递推公式了。
首先来看P数组的，P字符没有任何限制条件，可以跟在任何一个字符后面，所以有 P[i] = A[i-1] + P[i-1] + L[i-1]
再来看L数组的，L字符唯一的限制条件是不能有超过两个连续的L，那么在P和L字符后面可以加1一个L，如果前一个字符是L，我们要看再前面的一位是什么字符，如果是P或着A的话，可以加L，如果是L的话，就不能再加了，否则就连续3个了，所以有 L[i] = A[i-1] + P[i-1] + A[i-2] + P[i-2]
最后来看A数组的，这个比较麻烦，字符A的限制条件是整个字符串最多只能有1个A，那么当前一个字符是A的话，就不能再加A来，当前一个字符是P或者L的话，要确定之前从没有A出现过，才能加上A。那么实际上我们还需要定义两个数组P1, L1, 其中P1[i]表示数组[0,i]范围内以P结尾的不包含A的所有排列方式，L1[i]表示数组[0,i]范围内以L结尾的不包含A的所有排列方式，根据前两种情况我们不难推出P1和L1的递推公式，再加上A的递推公式如下：
A[i] = P1[i-1] + L1[i-1]
P1[i] = P1[i-1] + L1[i-1]
L1[i] = P1[i-1] + P1[i-2]
将第二第三个等式多次带入第一个等式，就可以将P1和L1消掉，可以化简为：
A[i] = A[i-1] + A[i-2] + A[i-3]
这样就可以少定义两个数组了，递推公式有了
https://discuss.leetcode.com/topic/86696/share-my-o-n-c-dp-solution-with-thinking-process-and-explanation
Before introducing the way to calculate the number of all possible attendance records with length n, we divide the problem into 3 parts.
As the attendance records is made by 3 charactors ('P', 'L', 'A'), the total number can be divided into

Total = ended with P + ended with L + ended with A.

If we define following series

T(n) is the total number of all possible attendance records with length n.

P(n) is the total number of all possible attendance records ended with 'P' with length n.

L(n) is the total number of all possible attendance records ended with 'L' with length n.

A(n) is the total number of all possible attendance records ended with 'A' with length n.

It can be inferred that

T(n) = A(n) + P(n) + L(n), n ≥ 1.

2.2 Solve the sub-problems by dynamic programming

As I use dynamic programming, I need to find out the recursive relation in 3 sub-problems.
2.2.1 CALCULATE P(N)
It can be inferred that

If we add a 'P' to an attendance records with length n - 1, we will get an attendance records ended with 'P' with length n.

For an attendance record with length n - 1,

  • If its (n - 1)th charactor is 'P' ---- CAN add 'P'. ("PP")

  • If its (n - 1)th charactor is 'A' ---- CAN add 'P'. ("AP")

  • If its (n - 1)th charactor is 'L' ---- CAN add 'P'. ("LP")

which means

P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.

and we have initial value for the recursive relation

A(1) = P(1) = L(1) = 1.

2.2.2 CALCULATE L(N)
Similarly,

If we add a 'L' to an attendance records with length n - 1, we will get an attendance records ended with 'L' with length n.

But the resulting attendance records must be regared as rewardable!
As the rule is that a record is regarded as rewardable if it doesn't contain

more than two continuous 'L' (late).

We need to consider the situations when we can add 'L' to an attendance record with length n - 1 and it's still regared as rewardable.
For an attendance record with length n - 1,

  • If its (n - 1)th charactor is 'P' ---- CAN add 'L'. ("PL")

  • If its (n - 1)th charactor is 'A' ---- CAN add 'L'. ("AL")

  • If its (n - 1)th charactor is 'L':

    • If its (n - 2)th charactor is 'A' ---- CAN add 'L'. ("ALL")

    • If its (n - 2)th charactor is 'P' ---- CAN add 'L'. ("PLL")

    • If its (n - 2)th charactor is 'L' ---- CAN NOT add 'L'. ("LLL" breaks the rule)

which means

L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3

and we have initial value for the recursive relation

A(1) = P(1) = 1.

A(2) = 2, P(2) = 3.

and

L(1) = 1, L(2) = 3.

2.2.3 CALCULATE A(N)
Similarly,

If we add a 'A' to an attendance records with length n - 1, we will get an attendance records ended with 'A' with length n.

But the resulting attendance records must be regared as rewardable!
As the rule is that a record is regarded as rewardable if it doesn't contain

more than one 'A' (absent).

We need to consider the situations when we can add 'A' to an attendance record with length n - 1 and it's still regared as rewardable.
For an attendance record with length n - 1,
  • If its (n - 1)th charactor is 'A' ---- CAN NOT add 'A'. ("AA" breaks the rule)
  • If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'A'.
  • If its (n - 1)th charactor is 'L' and has no 'A' ---- CAN add 'A'.
If we define series

noAP(n) is the total number of all possible attendance records ended with 'P' with length n and with no 'A'.

noAL(n) is the total number of all possible attendance records ended with 'L' with length n and with no 'A'.

It can be infered that

A(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

and we have initial value for the recursive relation

A(1) = 1.

noAP(1) = noAL(1) = 1.

2.2.4 CALCULATE NOAP(N) AND NOAL(N)
In 2.2.3, 2 new series noAP(n) and noAL(n) is introduced. Now, we focus on the recursive relation in noAP(n) and noAL(n).
For noAP(n), we need to consider the situations when we can add 'P' to an attendance record with length n - 1 and no 'A' and it's still regared as rewardable.
Since noAP(n) has no 'A', we don't need to consider the situation when its (n - 1)th charactor is 'A'.
For an attendance record with length n - 1, we can get only 2 situations
  • If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'P'.
  • If its (n - 1)th charactor is 'L' and has no 'A' ---- CAN add 'P'.
which means

noAP(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

and we have initial value for the recursive relation

noAP(1) = noAL(1) = 1.

For noAL(n), we need to consider the situations when we can add 'L' to an attendance record with length n - 1 and no 'A' and it's still regared as rewardable.
Since noAL(n) has no 'A', we don't need to consider the situation when its (n - 1)th charactor is 'A'.
For an attendance record with length n - 1, we can get
  • If its (n - 1)th charactor is 'P' and has no 'A' ---- CAN add 'L'.("PL")
  • If its (n - 1)th charactor is 'L' and has no 'A'.
    • If its (n - 2)th charactor is 'P' and has no 'A' ---- CAN add 'L'.("PLL")
    • If its (n - 2)th charactor is 'L' and has no 'A' ---- CAN NOT add 'L'.("LLL" breaks the rule.)
which means

noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

and we have initial value for the recursive relation

noAP(1) = noAL(1) = 1.

and

noAL(2) = 2.

2.3 Recursive relationship summarization

The answer to the whole problem is T(n), and

T(n) = A(n) + P(n) + L(n), n ≥ 1.

Recursive formula:

P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.

A(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

noAP(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3.

noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

with Initial value

A(1) = P(1) = L(1) = 1.

noAP(1) = noAL(1) = 1.

L(2) = 3.

noAL(2) = 2.

2.4 Simplifying

When n ≥ 4, the 3 formulas

A(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

noAP(n) = noAP(n - 1) + noAL(n - 1), n ≥ 2.

noAL(n) = noAP(n - 1) + noAP(n - 2), n ≥ 3.

can be simplified to

A(n) = A(n - 1) + A(n - 2) + A(n - 3), n ≥ 4.

Finally, the recursive formula group becomes

P(n) = A(n - 1) + P(n - 1) + L(n - 1), n ≥ 2.

L(n) = A(n - 1) + P(n - 1) + A(n - 2) + P(n - 2), n ≥ 3.

A(n) = A(n - 1) + A(n - 2) + A(n - 3), n ≥ 4.

Here, noAP(n) and noAL(n) disappeared.
with Initial value

P(1) = 1.

L(1) = 1, L(2) = 3.

A(1) = 1, A(2) = 2, A(3) = 4.

2.5 Do modulus

The result need to be returned after mod 10⁹ + 7.
Since the result is generated by adding a lot of middle results together, in order to make sure that every middle result and the final result won't exceed INT_MAX, we need to do mod for every middle result, and for every 2-middle-result-addition.

3. Complexity Analyse

3.1 Time complexity

Since the algothrim is one-pass from 1 to n.

The time complexity is O(n).

3.2 Space complexity

Since 3 arrays are used to save P(n), L(n), A(n), the total size is 3n.

The space complexity is O(n).

http://blog.csdn.net/zshouyi/article/details/71157585
    int checkRecord(int n) {
        int m = 1000000007;
        int *A = new int [n];
        int *P = new int [n];
        int *L = new int [n];
        
        P[0] = 1;
        L[0] = 1;
        L[1] = 3;
        A[0] = 1;
        A[1] = 2;
        A[2] = 4;
        
        if(n == 1) return 3;
        
        for(int i = 1; i < n; i++)
        {
            A[i - 1] %= m;
            P[i - 1] %= m;
            L[i - 1] %= m;
            
            P[i] = ((A[i - 1] + P[i - 1]) % m + L[i - 1]) % m;
            
            if(i > 1) L[i] = ((A[i - 1] + P[i - 1]) % m + (A[i - 2] + P[i - 2]) % m) % m;
            
            if(i > 2) A[i] = ((A[i - 1] + A[i - 2]) % m + A[i - 3]) % m;
        }
        
        return ((A[n - 1] % m + P[n - 1] % m) % m + L[n - 1] % m) % m;
    }


X.
http://www.cnblogs.com/grandyang/p/6866756.html
这道题是之前那道Student Attendance Record I的拓展，但是比那道题难度要大的多。从题目中说结果要对一个很大的数取余，说明结果是一个很大很大的数。那么一般来说这种情况不能用递归来求解，可能会爆栈，所以要考虑利用数学方法或者DP来做
我们定义一个三维的dp数组，其中dp[i][j][k] 表示数组前i个数字中，最多有j个A，最多有k个连续L的组合方式，那么我们最终要求的结果就保存在dp[n][1][2]中。然后我们来考虑如何求dp[i][j][k]，首先我们来取出前一个状态下的值，就是前i-1个数的值，dp[i-1][j][2]，即数组前i-1个数中，最多有j个A，最多有2个连续L的排列方式，然后如果j>0，那么再加上dp[i-1][j-1][2]，即加上了最多有j-1个A的情况，并对超大数取余；如果k>0，则再加上dp[i-1][j][k-1]，即加上了最多有j个A，最多有k-1个连续L的排列方式，其实博主并没有完全理解为什么要这么更新
https://leetcode.com/problems/student-attendance-record-ii/discuss/101633/Improving-the-runtime-from-O(n)-to-O(log-n)
Let f[i][j][k] denote the # of valid sequences of length i where:
  1. There can be at most j A's in the entire sequence.
  2. There can be at most k trailing L's.
We give the recurrence in the following code, which should be self-explanatory, and the final answer is f[n][1][2].
public int checkRecord(int n) {
    final int MOD = 1000000007;
    int[][][] f = new int[n + 1][2][3];

    f[0] = new int[][]{{1, 1, 1}, {1, 1, 1}};
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 3; k++) {
                int val = f[i - 1][j][2]; // ...P
                if (j > 0) val = (val + f[i - 1][j - 1][2]) % MOD; // ...A
                if (k > 0) val = (val + f[i - 1][j][k - 1]) % MOD; // ...L
                f[i][j][k] = val;
            }
    return f[n][1][2];
}
The runtime of this solution is clearly O(n), using linear space (which can be easily optimized to O(1) though). Now, let's see how to further improve the runtime.
In fact, if we treat f[i][][] and f[i-1][][] as two vectors, we can represent the recurrence of f[i][j][k] as follows:
f[i][0][0]   | 0 0 1 0 0 0 |   f[i-1][0][0]
f[i][0][1]   | 1 0 1 0 0 0 |   f[i-1][0][1]
f[i][0][2] = | 0 1 1 0 0 0 | * f[i-1][0][2]
f[i][1][0]   | 0 0 1 0 0 1 |   f[i-1][1][0]
f[i][1][1]   | 0 0 1 1 0 1 |   f[i-1][1][1]
f[i][1][2]   | 0 0 1 0 1 1 |   f[i-1][1][2]
Let A be the matrix above, then f[n][][] = A^n * f[0][][], where f[0][][] = [1 1 1 1 1 1]. The point of this approach is that we can compute A^n using exponentiating by squaring (thanks to @StefanPochmann for the name correction), which will take O(6^3 * log n) = O(log n) time. Therefore, the runtime improves to O(log n), which suffices to handle the case for much larger n, say 10^18.
Update: The final answer is f[n][1][2], which involves multiplying the last row of A^n and the column vector [1 1 1 1 1 1]. Interestingly, it is also equal to A^(n+1)[5][2] as the third column of A is just that vector


Update: The final answer is f[n][1][2], which involves multiplying the last row of A^n and the column vector [1 1 1 1 1 1]. Interestingly, it is also equal to A^(n+1)[5][2] as the third column of A is just that vector. Credit to @StefanPochmann.
e:
final int MOD = 1000000007;
final int M = 6;

int[][] mul(int[][] A, int[][] B) {
    int[][] C = new int[M][M];
    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            for (int k = 0; k < M; k++)
                C[i][j] = (int) ((C[i][j] + (long) A[i][k] * B[k][j]) % MOD);
    return C;
}


int[][] pow(int[][] A, int n) {
    int[][] res = new int[M][M];
    for (int i = 0; i < M; i++)
        res[i][i] = 1;
    while (n > 0) {
        if (n % 2 == 1)
            res = mul(res, A);
        A = mul(A, A);
        n /= 2;
    }
    return res;
}

public int checkRecord(int n) {
    int[][] A = {
            {0, 0, 1, 0, 0, 0},
            {1, 0, 1, 0, 0, 0},
            {0, 1, 1, 0, 0, 0},
            {0, 0, 1, 0, 0, 1},
            {0, 0, 1, 1, 0, 1},
            {0, 0, 1, 0, 1, 1},
    };
    return pow(A, n + 1)[5][2];
}
https://discuss.leetcode.com/topic/86479/o-n-time-o-1-space-solutionhttp://code.bitjoy.net/2017/04/26/leetcode-student-attendance-record-ii/
显然是DP问题，不过是三维DP。令dp[n][i][j]表示长度为n的字符串，包含i个'A'并且以j个'L'结尾的字符串个数。那么有如下的递推公式：
dp[n][0][0]=sum(dp[n-1][0])：要求长度为n、包含0个'A'，且以0个'L'结尾的字符串个数；所以前n-1肯定也只包含0个'A'，但是前n-1可以以0、1或2个'L'结尾，因为我第n个字符不放'L'就能保证前n以0个'L'结尾。所以dp[n][0][0]=sum(dp[n-1][0])。其他的类似分析有：
  • dp[n][0][1]=dp[n-1][0][0]
  • dp[n][0][2]=dp[n-1][0][1]
  • dp[n][1][0]=sum(dp[n-1][0])+sum(dp[n-1][1])
  • dp[n][1][1]=dp[n-1][1][0]
  • dp[n][1][2]=dp[n-1][1][1]
    long long getSum(vector<int>& v) {
        long long ans = 0;
        for(const int &i : v) ans += i;
        return ans % kMOD;
    }
    int checkRecord(int n) {
        vector<vector<int>> dp = {{1, 1, 0}, {1, 0, 0}};
        for(int i = 2; i <= n; ++i){
            vector<vector<int>> ndp = {{0, 0, 0}, {0, 0, 0}};
            ndp[0][0] = getSum(dp[0]);
            ndp[0][1] = dp[0][0];
            ndp[0][2] = dp[0][1];
            ndp[1][0] = (getSum(dp[1]) + getSum(dp[0])) % kMOD;
            ndp[1][1] = dp[1][0];
            ndp[1][2] = dp[1][1];
            dp = ndp;
        }
        return (getSum(dp[0]) + getSum(dp[1])) % kMOD;
    }
X. DP
http://bookshadow.com/weblog/2017/04/16/leetcode-student-attendance-record-ii/
动态规划（Dynamic Programming）
利用dp[n][A][L]表示长度为n，包含A个字符'A'，以L个连续的'L'结尾的字符串的个数。
状态转移方程：
dp[n][0][0] = sum(dp[n - 1][0])
dp[n][0][1] = dp[n - 1][0][0]
dp[n][0][2] = dp[n - 1][0][1]
dp[n][1][0] = sum(dp[n - 1][0]) + sum(dp[n - 1][1])
dp[n][1][1] = dp[n - 1][1][0]
dp[n][1][2] = dp[n - 1][1][1]

初始令dp[1] = [[1, 1, 0], [1, 0, 0]]
由于dp[n]只和dp[n - 1]有关，因此上述转移方程可以使用滚动数组，将空间复杂度降低一维。
private final int MOD = 1000000007; public long sum(int[] nums) { long ans = 0; for (int n : nums) ans += n; return ans % MOD; } public int checkRecord(int n) { int dp[][] = {{1, 1, 0}, {1, 0, 0}}; for (int i = 2; i <= n; i++) { int ndp[][] = {{0, 0, 0}, {0, 0, 0}}; ndp[0][0] = (int)sum(dp[0]); ndp[0][1] = dp[0][0]; ndp[0][2] = dp[0][1]; ndp[1][0] = (int)((sum(dp[0]) + sum(dp[1])) % MOD); ndp[1][1] = dp[1][0]; ndp[1][2] = dp[1][1]; dp = ndp; } return (int)((sum(dp[0]) + sum(dp[1])) % MOD); }

X.
http://www.cnblogs.com/grandyang/p/6866756.html
这里面定义了两个数组P和PorL，其中P[i]表示数组前i个数字中已P结尾的排列个数，PorL[i]表示数组前i个数字中已P或者L结尾的排列个数。这个解法的精髓是我们先不考虑字符A的情况，而是先把定义的这个数组先求出来，由于P字符可以再任意字符后面加上，所以 P[i] = PorL[i-1]；而PorL[i]由两部分组成，P[i] + L[i]，其中P[i]已经更新了，L[i]只能当前一个字符是P，或者前一个字符是L且再前一个字符是P的时候加上，即为P[i-1] + P[i-2]，所以PorL[i] = P[i] + P[i-1] + P[i-2]。
那么我们就已经把不包含A的情况求出来了，存在了PorL[n]中，下面就是要求包含一个A的情况，那么我们就得去除一个字符，从而给A留出位置。那么就相当于在数组的任意一个位置上加上A，那么数组就被分成左右两个部分了，而这两个部分当然就不能再有A了，实际上所有不包含A的情况都已经在数组PorL中计算过了，而分成的子数组的长度又不会大于原数组的长度，所以我们直接在PorL中取值就行了，两个子数组的排列个数相乘，然后再把所有分割的情况累加起来就是最终结果啦

https://leetcode.com/problems/student-attendance-record-ii/discuss/101638/Simple-Java-O(n)-solution
P[i] = PorL[i - 1]; //this line means ending with P, just appending P in PorL
PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M; //P[i] end with P, P[i-1], end with one L(or PL), P[i-2], end with two L(or LL).
and last logic ,res init value with PorL without A, and add one A to the sequence.
long res = PorL[n];
for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
long s = (PorL[i] * PorL[n - i - 1]) % M;
res = (res + s) % M;
}
static final int M = 1000000007;

public int checkRecord(int n) {
    long[] PorL = new long[n + 1]; // ending with P or L, no A
    long[] P = new long[n + 1]; // ending with P, no A
    PorL[0] = P[0] = 1; PorL[1] = 2; P[1] = 1;

    for (int i = 2; i <= n; i++) {
        P[i] = PorL[i - 1];
        PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M;
    }
    
    long res = PorL[n];
    for (int i = 0; i < n; i++) { // inserting A into (n-1)-length strings
     long s = (PorL[i] * PorL[n - i - 1]) % M;
        res = (res + s) % M;
    }
    
    return (int) res;
}

X. DP3
https://leetcode.com/problems/student-attendance-record-ii/discuss/101634/Python-DP-with-explanation
dp[i]the number of all possible attendance (without 'A') records with length i :
  • end with "P": dp[i-1]
  • end with "PL": dp[i-2]
  • end with "PLL": dp[i-3]
  • end with "LLL": is not allowed
so dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
the number of all possible attendance (with 'A') records with length n:
∑dp[i] *dp[n-1-i] i = 0,1,...,n-1
Time Complexity O(n)
Space Complexity O(n)
(In code nums[i+1] means dp[i])
    def checkRecord(self, n):
        if n == 1:
            return 3
        if n == 0:
            return 0
        nums = [1, 1, 2]
        i = 2
        while i < n:
            nums.append((nums[i] + nums[i-1] + nums[i-2])% 1000000007)
            i += 1
        result = (nums[n] + nums[n-1] + nums[n-2]) % 1000000007
        for i in range(n):
            result += nums[i+1] * nums[n-i] % 1000000007
            result %= 1000000007
        return result
https://leetcode.com/problems/student-attendance-record-ii/discuss/101652/Java-4-lines-DP-solution-with-state-transition-table-explained
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;                   
}
http://www.voidcn.com/article/p-dqtnscph-bpk.html
dp数组内分为六种情况：
A0L0: 
  A0L1: 
  A0L2:
  A1L0: 
  A1L1:
  A1L2:
AxLy表示当前字符串中一共x个A，结尾处一共连续y个L
    public int checkRecord(int n) {
        int[] dp = {1, 1, 0, 1, 0, 0};
        for (int i = 2; i <= 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);
    }
    private int sum(int[] dp, int start, int end) {
        final int MOD = 1000000007;
        int res = 0;
        for (int i = start; i <= end; i++) {
            res = (res + dp[i]) % MOD;
        }
        return res;
    }


at
Labels: , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts