Python DP with explanation


  • 19
    Z

    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
    

  • 4

    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;
    }
    

  • 0
    1

    @zym_ustc said in Python DP with explanation:

    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 ?


  • 5
    G

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


  • 3

    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

  • 0
    F

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


  • 1
    H

    @zym_ustc said in Python DP with explanation:

    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

  • 0
    D
    This post is deleted!

  • 0
    S

    @greenmoon55 said in Python DP with explanation:

    @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.


  • 0
    S

    @suneelg said in Python DP with explanation:

    @greenmoon55 said in Python DP with explanation:

    @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.


  • 0
    S

    @honda000 said in Python DP with explanation:

    nums = [1, 1, 2]

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


  • 0
    Y

    @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")

    Hope this could help you to get through it.


  • 0

    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?


  • 0
    Z

    @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']


  • 0

    @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.


  • 0
    S

    @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


Log in to reply
 

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