Leetcode discuss | 552. Student Attendance Record II | My C# practice

July 10, 2021

Here is the link. 

C# | Hard level DP problem | Three states | Top down

July 10, 2021
Introduction
It is time for me to code a solution using C# and understand most important is my crafting skills. I have not submitted any code on Leetcode at least three weeks. If I choose to be consistent, then it is time for me to make corrections, and go back to code the idea for those hard level Leetcode premium algorithms with Google tag.

DP solution | Three states | Top down
I do think that it is easy to write if I can take an approach to write down detail about how to solve n = 2 with 8 possible solutions.

The detail discussion is here. I wrote down to warmup and it took me a few hours.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode552_studentAttendance
{
    class Program
    {
        static void Main(string[] args)
        {
            var result = CheckRecord(2);
            Debug.Assert(result == 8);
        }

        /// <summary>
        /// DP solution, top down
        /// Three states: 
        /// state 1: length of sequence
        /// state 2: total A in the sequence, suffix of sequence
        /// state 3: count of continuous 'L', suffix of sequence
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int CheckRecord(int n)
        {
            // state 2: 'A' - 0 or 1
            // state 3: 'L' - 0 or 1 or 2
            var dp = new int[n + 1, 2, 3];
            for(int index = 0 ; index < n + 1; index++)
            {
                for(int countA = 0; countA < 2; countA++)
                {
                    for(int countL = 0; countL < 3; countL++)
                    {
                        dp[index, countA, countL] = -1; 
                    }
                }
            }

            return topDownTotalCount(n, 0, 0, dp);
        }

        /// <summary>
        /// This one is challenge, top down
        /// Memoization
        /// Subproblem | three states | suffix 
        /// Take care of those above three key things
        /// </summary>
        /// <param name="n"></param>
        /// <param name="suffixA"></param>
        /// <param name="suffixContinuousL"></param>
        /// <param name="dp"></param>
        /// <returns></returns>
        private static int topDownTotalCount(int n, int suffixA, int suffixContinuousL, int[,,] dp)
        {
            var mod = 1000 * 1000 * 1000 + 7; 
            
            // base case 
            if(n == 0)
            {
                return 1; 
            }

            if(dp[n, suffixA, suffixContinuousL] != -1)
            {
                return dp[n, suffixA, suffixContinuousL];
            }

            int count = 0; 
            if(suffixA == 0)
            {
                // add 'A', reset continuous L
                count += topDownTotalCount(n - 1, suffixA + 1, 0, dp);
                count %= mod;
            }

            if(suffixContinuousL < 2)
            {
                // add 'L', suffixContinuousL++
                // suffixA - no change
                count += topDownTotalCount(n - 1, suffixA, suffixContinuousL + 1, dp);
                count %= mod; 
            }

            // add 'P'
            // reset suffixContinuousL = 0
            count += topDownTotalCount(n - 1, suffixA, 0, dp);
            count %= mod; 

            // memoization - save the count variable
            dp[n, suffixA, suffixContinuousL] = count; 

            return count; 
        }
    }
}