Leetcode discuss: 1246. Palindrome Removal

 Jan. 21, 2021

Here is the link. 

First practice - C# - DP - Patience

Jan. 21, 2021
Introduction
It is the last algorithm in Leetcode premium Microsoft mock onsite. I could not finish the code in mock interview. I understood that it can be solved using brute force all possible subproblems using two dimension dynamic programming.

Case studies
It is important for me to play with the following test cases first, understand the value of minimum move, and then write a solution to match the analysis.
Case 1:
[1, 3, 4, 1], it should be 2, not 3. I wrote the code and then failed the test case by online judge. And then I learned to analyze the case. Remove 4, [1, 3, 1] should be able to be removed once since it is palindrome.
Case 2:
[1, 3, 4, 1, 5], it should be 3, not 4. One of solutions is to remove 4 first, then remove [1, 3, 1], and then remove [5].
Lessons I learn:

1. Make sure that all possible answers are considered from 1 to 2 to bigger number.
2. Edge case - take first number and last number out, solve [3, 4, 1] first. This idea can lead to answer 1 as minimum move, it is the only way. All other ways has at least 2 minimum moves.
3. Brute force all possible ways to break into subproblems.

Time spent
I spent more than two hours to make it work. It is important for me to work independently, since I already solved over 600 algorithms. I like to trian myself to think hard, longer, and solve a hard level algorithm by myself.

Continue to simplify
After the first success submission and writing of this post, I spent another 15 minutes to simplify the code, remove redudant code, and make it concise and working.

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

namespace minimumMove
{
    class Program
    {
        static void Main(string[] args)
        {
            //var result = MinimumMoves(new int[]{1, 3, 4, 1});
            //var result = MinimumMoves(new int[] { 1, 3, 4, 1, 5 }); 
            var result = MinimumMoves(new int[] { 19, 4, 9, 11, 19 }); 
        }

        /// <summary>
        /// Leetcode - 1246. Palindrome Removal
        /// </summary>
        /// <param name="arr"></param>
        /// <returns></returns>
        public static int MinimumMoves(int[] arr)
        {
            if (arr == null || arr.Length == 0)
                return 0;

            var n = arr.Length;
            var dp = new int[n, n];

            dp[0, 0] = 1;
            for (int end = 1; end < n; end++)
            {
                // dp[0, end], ..., dp[end - 1, end] backward          
                dp[end, end] = 1;
                for (int i = 1; i <= end; i++)
                {
                    var left = end - i;
                    var right = end;

                    // [1, 3, 4, 1], dp[0, 3] = 2, not 3,
                    var bothEndSame = arr[left] == arr[right];

                    var count = right - left + 1;
                    var min = count;

					var dpCenter = 0; 
                    if (count > 2)
                    {
                       dpCenter = dp[left + 1, right - 1]; // exclude both ends
                    }
                   
                   min = 2 + dpCenter;
                   if (bothEndSame)
                   {
                     min = dpCenter; // [1, 2, 3, 4, 1]     
                     if(count == 2)
                     {
                         min = 1; 
                     }                                                                    
                   }                   

                    for (int k = left + 1; k <= end; k++)  // [1, 3, 4, 1, 5] -> dp[0, 3] + dp[4, 4]
                    {
                        min = Math.Min(min, dp[left, k - 1] + dp[k, end]);
                    }

                    dp[left, end] = min;
                }
            }

            return dp[0, n - 1];
        }
    }
}