Leetcode Challenge for 30days

Dynamic programming

I am going to solve all hard level dynamic programming questions in Leetcode within two weeks and write down all the solution, thoughts about the questions.

Day 1

• Longest Valid Parentheses (50mins solved)
• Count Palindromic Subsequences (100 mins solved)
• Number of Ways to Separate Numbers (8hrs solved)
• Longest Increasing Path in a Matrix (15 mins)
• Maximum Sum of 3 Non-Overlapping Subarrays (2.5hrs solved) (OMG this question is so easy, i stucked at a little bug, fk me)
• Wildcard Matching (45mins) (forgot to initilize the dp array with edge cases)

Reflection

I watched a youtube video talks about blackbox method, do not focus on the detail 
first, make some assumptions, like if I can solve this subproblem what should 
I do next. I now can narrow down the compleixty of a problem. However, the 
speed is still under the bar, maybe I could improve by doing more and more questions.

-> Number of Ways to Separate Numbers is most difficult one, I have ever done. Many 
technics such as suffix array and prefix sum of the dp subproblem, are very useful 
and blew my mind. 

Day 2

• Number of Submatrices That Sum to Target + Subarray Sum Equals K(3hr solved)
• Maximize Palindrome Length From Subsequences + Longest Palindromic Subsequence(45mins solved)
• Burst Balloons (30mins)
• Number of Beautiful Partitions (5 hrs)
• Maximum Deletions on String (30mins)
• Decode Ways II (40mins)

Reflection

Many question used suffix and prefix idea to optimize the complexity,
and there is a pattern, when you find out the question is three pass like question, 
you can use prefix sum and suffix sum, to reduce an O(N) complexity,
the most interesting question is Number of Submatrices That Sum to Target + Subarray
Sum Equals K, when you solve the same question in 1d array, and use the same idea in 2d
array, this conversion is enlightened.

Day 3

• Count Increasing Quadruplets (3 hrs)
• Partition Array Into Two Arrays to Minimize Sum Difference (15mins)
• Maximum Total Beauty of the Gardens (3 hrs)
• Subsequence With the Minimum Score (12hrs)
• Last Substring in Lexicographical Order (30mins)
• Closest Subsequence Sum (18mins)

Reflection

I can say i mastered the idea of meet in middle and bitmask, many question in this
problem set can be transferred to two sum problem, which is very smart and clear.

Day 4

• Split Array With Same Average (1hr)
• Count the Number of Ideal Arrays (5hrs)
• Regular Expression Matching
• Parallel Courses II (I cannot solve this, i used greedy, but this is NP problem, when i knew this is a brute force problem, i just used 15mins to solve)
• Largest Multiple of Three

Day 5

• Number of Great Partitions
• Kth Ancestor of a Tree Node
• Palindrome Partitioning II
• The Score of Students Solving Math Expression
• Number of Digit One