1
\$\begingroup\$

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 10^9 + 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).

Link to this question on leetcode is here

I was able to come up with a recursive approach but could not memoize it like in DP. I want to use the same approach but with memoization. Below is my submitted code.

public class Solution {

    public long count = 0;
    public int checkRecord(int n) {

        func(1,n,0,0);
        return (int)count % (1000000007) ;

    }

    public void func(int pos , int n , int alreadyAbsent , int countOfLate)
    {
        if(pos > n)
        {
            count++;
        }
        else
        {
            func(pos + 1, n , alreadyAbsent,0);
            if(countOfLate < 2)
            {
                func(pos + 1,n,alreadyAbsent,countOfLate + 1);
            }
            if(alreadyAbsent == 0)
            {
                func(pos + 1,n,1,0);
            }
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

First of all, java doesn't like deep recursive calls. I tried running the following mini program on my machine and it only went up to 11398 before ending with a stackoverflow:

public static void main(String[] args) throws Exception {
    recurseTest(0);
}

public static void recurseTest(int n){
    System.out.println(n);
    recurseTest(n+1);
}

Notice that this only stores an int each call.

So you're better of calculating everything in a for loop instead.


It would be nice if we could do a single pass over the entire record choosing which letter to add at that step and update our total (+ helper totals). That way we don't even need to consider memoisation.

Let's look at which totals we want to keep track of to calculate the correct result.

First we have the requirement that the entire string can only have at most 1 letter A. So I would keep track of 2 groups of totals. Those that don't have an A yet. And those that do.

Next we must ensure that we can have at most 2 consecutive Ls. So let's keep track of how many L's are in the end at the previous step.

This leads to the following 6 variables.

long noA0;
long noA1;
long noA2;
long a0;
long a1;
long a2;

where noAx means it doesn't contain an A yet and ends with x letters L.

Here's what we would like to write in each step to update to the new values:

noA0 = noA0 + noA1 + noA2; //added P to any of the previous noA's
noA1 = noA0;
noA2 = noA1;
a0 = noA0 + noA1 + noA2 + a0 + a1 + a2; //added A to noA_ or added P to a_
a1 = a0;
a2 = a1;

But that has the problem that we are using updated values already. So we need to store some temp values instead.

tempnoA0 = noA0 + noA1 + noA2; //added P to any of the previous noA's
tempa0 = noA0 + noA1 + noA2 + a0 + a1 + a2; //added A to noA_ or added P to a_    
noA2 = noA1;
noA1 = noA0;
a2 = a1;
a1 = a0;
noA0 = tempnoA0;
a0 = tempa0;

Now all you have to do is run this in a loop and figure out what the actual end result is. But that shouldn't be too hard right?


A last thing to consider is when to do the modulo. It may well be worth doing this at the right times during the loop as well to reduce the risk of overflowing the long (although I didn't actually look if this would be a real problem or not).

\$\endgroup\$
  • \$\begingroup\$ In the current state of your code, noA2 and a2 are assigned the wrong values because noA1 and a1 have already been reassigned. Switching the order of the assignments of noA1 and noA2, and a1 and a2 respectively, would rectify this issue without additional temporary variables. \$\endgroup\$ – Stingy Jul 23 '17 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.