Leetcode discuss: 552. Student Attendance Record II

 Here is the link. 

First practice - C# - 30 hard level - DP

Dec. 7, 2020
Introduction
It is my one day project to work on 30 hard level algorithms based on Leetcode premium, Google, hard level.

DP - learning
I thought about using dynamic programming, and I need to learn how to find three states, length of sequence, total number of 'A', continuous 'L'.

I just came cross this solution shared here, and I wrote my own using C#.

30 Hard level algorithms
I am planning to study those 30 algorithms in a day to prepare for my onsite interview.

Top 10 are the following:

• 727 Minimum windows subsequence - DP, sliding window
• 715 Range Modulde, Segment tree, ordered map
• 552 Student attendance record II, DP
• 465 Optimal accont balancing
• 1499 Max value of equation, Array, sliding window
• 753 Cracking the safe, math, DFS
• 1231 Divide Chocolate, Binary search, greedy
• 308 Range sum query 2D - Mutable, Binary indexed tree, segment tree
• 1293 Shortest path in a grid with obstacles elimination
• 1444 Number of ways of cutting a pizza, DP

public class Solution {
    public int CheckRecord(int n) {
        var cache = new int[n+1, 2, 3];
        
        for(int row = 0; row < n + 1; row++)
        {
            for(int col = 0; col < 2; col++)
            {
                for(int L = 0; L < 3; L++)
                {
                    cache[row, col, L] = -1; 
                }
            }
        }
        
        return helper(n, 0, 0, cache);
    }

    // Returns the number of ways to create a string of 
    // length n with characters 'A', 'L', 'P' 
    // while having <= 1 total 'A's and <= 2 consecutive 'L's.
    // n = 1, return 3 'A' or 'P' or 'L'
    private int helper(int n, int totalA, int continuousL, int[,,] cache) 
    {
        int mod = 1000 * 1000 * 1000 + 7;
        // base case - 1, 
        if (n == 0)
        {
            return 1;
        }
        
        if (cache[n, totalA, continuousL] != -1)
        {
            return cache[n, totalA, continuousL];
        }
    
        int result = 0;
        
        if (totalA == 0) {
            // add 'A', reset continuousL = 0
            // n -> n - 1
            result += helper(n - 1, totalA + 1, 0, cache);              // Choose 'A'
            result %= mod;
        }
    
        if (continuousL < 2) {
            // add 'L', continuousL++
            // totalA - no change 
            result += helper(n - 1, totalA, continuousL + 1, cache);    // Choose 'L'
            result %= mod;
        }
    
        // add 'P'
        // reset continuousL = 0
        // totalA - no change 
        result += helper(n - 1, totalA, 0, cache);                      // Choose 'P'
        
        result %= mod;
        
        // memoization - save to cache
        cache[n, totalA, continuousL] = result;
        
        return result;
    }
}