# 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]`)

``````class Solution(object):
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
``````

• Similar approach in Java.

``````static final int M = 1000000007;

public int checkRecord(int n) {
long[] PorL = new long[n + 1]; // ending in P or L, no A
long[] P = new long[n + 1]; // ending in 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
long s = (PorL[i] * PorL[n - i - 1]) % M;
res = (res + s) % M;
}

return (int) res;
}
``````

• the number of all possible attendance (with 'A') records with length n:
∑dp[i] *dp[n-1-i] i = 0,1,...,n-1

Could you please explain above in more details ?

• @1mp0ss1ble It means you can split the array in all possible places and then insert A.

• Just a variation...

``````def checkRecord(self, n):
if n < 2:
return n * 3
nums = [1]
while len(nums) <= n + 1:
nums.append(sum(nums[-3:]) % 1000000007)
return sum(map(operator.mul, nums[:-1], nums[:0:-1])) % 1000000007``````

• @1mp0ss1ble
maybe ∑(dp[i] *dp[n-1-i]) i = 0,1,...,n-1 more clear :)

• nums = [1, 1, 2]

why init nums to [1,1,2]? how it comes?

update:
i use the real value:
i=0, possible =1
i=1, possible =2 (P,L)
i=2, possible =4 (PP,PL,LP,LL)

``````    def checkRecord(self, n):
"""
:type n: int
:rtype: int
"""
if n==1:return 3
if n==0: return 0
mod=1000000007
dp=[0 for i in xrange(n+1)]
dp[0],dp[1],dp[2]=1,2,4
for i in range(3,n+1):
dp[i]=(dp[i-1]+dp[i-2]+dp[i-3] )% mod
res=dp[n]
print dp
for i in xrange(1,n+1):
res+=dp[i-1]*dp[n -i]%mod
res=res%mod
return res``````

• This post is deleted!

• @1mp0ss1ble It means you can split the array in all possible places and then insert A.

Sorry, I still don't get how ∑(dp[i] *dp[n-1-i]) i = 0,1,...,n-1 gives all possibles ways of inserting A into dp[n]. Would really appreciate some explanation. Thanks.

• @1mp0ss1ble It means you can split the array in all possible places and then insert A.

Sorry, I still don't get how ∑(dp[i] *dp[n-1-i]) i = 0,1,...,n-1 gives all possibles ways of inserting A into dp[n]. Would really appreciate some explanation. Thanks.

Never mind. I expanded the expression and it now makes sense. For n=3, it becomes dp0dp2+dp1dp1+dp2dp0, When you place A at pos1, then P&L can be placed in dp0dp2 ways.

• nums = [1, 1, 2]

I didn't get nums = [1, 1, 2] too. Your code is easier to understand.

• @suneelg It takes me a while to figure it out. Just as he said "In code nums[i+1] means dp[i]", here is the relationships:

dp[1] = nums[1 + 1] = nums[2] = 2 ("P", "L")
dp[0] = nums[0 + 1] = nums[1] = 1 ("")
dp[-1] = nums[-1 + 1] = nums[0] = 1

You can figure it out by computing the value for dp[2].

dp[2] = nums[2 + 1] = nums[3] = 4 ("LP", "PP", "PL", "LL")

• I don't understand the logic.
dp[i] stands for the number of all possible attendance (without 'A') records with length `i` but dp[i-1] stands for sequence that ends with "P"? Is there a conflict?

• @jedihy
`dp[i] = dp[i].[end with 'P'] + dp[i].[end with 'PL'] + dp[i].[end with 'PLL'] + dp[i].[end with 'LLL']`

• `dp[i-1]` is the number of all possible attendance (without `'A'`) records with length `i-1`.
For each one it can push_back a `'P'`(still valid) to get a record whose length is `i`.

• For each record ending with `'P'` whose length is `i`, we can pop_back `'P'` to get a record (still valid) whose length is `'i-1'`.

So, `dp[i-1]` = `dp[i].[ends with 'P']`

It doesn't mean `dp[i-1]` = `dp[i-1].[ends with 'P']`

• @zym_ustc I got it. "P", "PL", "PLL" are just like separators for generating new valid records and by doing so, those previous dp values could be used.

• @honda000
I think that is because he shift one position , he said `(In code nums[i+1] means dp[i])`

[1, 1, 2 ] ==> [ 1, 1, 2, 4], it's actually same

• @dettier good clean code.

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