Related: LeetCode 551 - Student Attendance Record I
https://leetcode.com/problems/student-attendance-record-ii
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)
https://discuss.leetcode.com/topic/86479/o-n-time-o-1-space-solutionhttp://code.bitjoy.net/2017/04/26/leetcode-student-attendance-record-ii/
X. DP
http://bookshadow.com/weblog/2017/04/16/leetcode-student-attendance-record-ii/
X.
http://www.cnblogs.com/grandyang/p/6866756.html
https://leetcode.com/problems/student-attendance-record-ii/discuss/101638/Simple-Java-O(n)-solution
X. DP3
https://leetcode.com/problems/student-attendance-record-ii/discuss/101634/Python-DP-with-explanation
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:
- 'A' : Absent.
- 'L' : Late.
- '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.
http://blog.csdn.net/zshouyi/article/details/71157585The space complexity is O(n).
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:- There can be at most
j
A's in the entire sequence. - 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
Update: The final answer is
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];
}
显然是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;
}
http://bookshadow.com/weblog/2017/04/16/leetcode-student-attendance-record-ii/
动态规划(Dynamic Programming)
状态转移方程:
由于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).
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;
}
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
Space 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
For example:
AnLn
denote number of strings containing n A
's and ending with n L
'sFor 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:
and so on...
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:
and so on...
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;
}