279 - Perfect Squares

Dynamic Programming

5 - Longest Palindromic Substring

Two dimensions dp problem. First of all, create a $n \times n$ dp array, where dp[i,j] means whether substring[i,j] is palindromic.

Secondly, iterate the string, pay attention to the iteratation direction, the update rules is:

dp[i,i] = True because only one character is palindromic.

dp[i,j] = True if i+1 == j, i.e., two chars are next to each other and same

True if i+1<j and dp[i+1, j_1] is true and two charaters are same
62 - Unique Paths

Collecting apples problem.
63 - Unique Paths II

Same to the above problem. The only different is how to initialize the dp.
64 - Minimum Path Sum

Collecting apples problem.
91 - Decode Ways

In essence, it is same as the Q-70 but with more requirements. Create a one dimension array dp, dp[i] denoting the total ways string[0, i]. The updating rule is:

if current char is not 0, then dp[i] = dp[i-1]

if current char plus previous char is between 10 and 26, dp[i] += dp[i-2]

Be careful when the input starts with ‘0’ like “01”.
96 - Unique Binary Search Trees

Very tricky. dp[i] means the ways of creating bst if there are i nodes. so if there are i+1 nodes, then we pick any node and as a root, say k, and then nodes < k forms left subtree whiel nodes > k forms the right tree, therefore dp[i+1] = dp[k] * dp[i+1-k] for k from 1 to i+1
53 - Maximum Subarray

One dimmension dp problem, but remember to return the max(dp) instead of dp[-1].
70 - Climbing Stairs

create a dp array, each element denotes the ways to reach if taking i steps.
120 - Triangle

collecting apples. Just a vertical version.
121 - Best Time to Buy and Sell Stock

create a temporary variabe cur_min = prices[0]. Iterate the prices, there are only two situations:

first one: current price is greater than the cur_min, then we can compute the profit.

second one: current price is lower than the cur_min, then we update the cur_min.
139 - Word Break

The input size determines the dp array. The input is a string, so the dp array is one dimension. dp[i] array means whether string[0:i+1] can be formed by wordDict.
152 - Maximum Product Subarray

Very similar to Maximum Sum Subarray. But in product operation, nnegative negative could result in a positive value, which makes it different from the Sum problem. Therefore, we need to create two dp arrays, one for max_ and one for min_. Each time, the dp_max[i] = max(e, dp_max[i-1] \ e, dp_min[i-1] * e). Same with dp_min[i].
198 - House Robber

create a dp array, each element denotes the maximum values you steal when you are in this index.
213 - House Robber II

The difference is that hourses are arranged in a circle. So we can only rob first house, or only rob las house, or don’t rob both houses. So we can use two dp arrays, one for houses without first house; the other dp array for houses without last house. Pay attention to the initial conditions: i.e., len(houses) = 0|1
221 - Maximal Square

create a two-d dp array, dp[i , j] means the the maximum square when point(i,j) is the botton-right point. So the updating rule is when matrix(i,j) is 1, then we need to check dp(i-1,j-1) and the row i and colum j. As for the checking row and column, we can subtitute it with checking dp array. Checking row i equals dp(i,j-1) is 1. The same case with column.
279 - Perfect Squares

A new type of dp problem. Like coin changes. It is hard to thnk of how to iterate the “input array”. Create the dp array, dp[i] is the least number of perfect number to form number i. Then dp[i] = min(dp[i], dp[i-perfect number]+1).
300 - Longest Increasing Subsequence

kind of similar to Q-279. They have very similar way to iterate the input. Instead of just checking the previous number (i-1), we need to check all previous numbers (1,2, …, i-1).
303 - Range Sum Query - Immutable

Two ways: Dynamic and Statistic.

Dynamic: sum(nums[i:j+1])

Statistic: given the arrays, compute the accumulative sum. And then given the index i and j, return accumulative_sum[j]-accumulative_sum[i-1].
304 - Range Sum Query 2D - Immutable

When inplementing, pay attention to two sitautions: if input is None, then just return; if matrix is [[1]] and query is [0,0,0,0], you need to expand the dp array.
322 - Coin Change

classical problem.
338 - Counting Bits

Kind of math problems. It is hard to classify it as dp problem. Actually, we can find that 2, 4, 8, .. are 10, 100, 1000,… which only conatin one ‘1’, we call it base number. Then non-base number = base + off-set. So, the number of 1 of number is = 1 (from base) + 1 from (number - base).
343 - Integer Break

The updating rule is so tricky.
368 - Largest Divisible Subset

The idea is straightford but the implementation needs so much attention.
Very difficult. Find out the least money to win the game. So it is a min problem, which means for a dp array, dp[i] means the money we need to win, and the result is min(dp[i]). Then, we need to figure out how to compute the dp[i]. dp[i] requires that we win the game and thus we need to consider all cases that we win and choose the worst case as dp[i], which is max problem. So, how do you consider all the cases when given a i?
1. It is hard to come up with the two-dimensions dp array.
2. As for the updating rule, for example n=2, because you try to seek the worst scenario, you have to guess 1 first and then 2, so you cost is 1. If n=3, you have two choices: guess 1 then guess 2; or guess 2 then guess 1. But choose the worst scenario.
3. So for n, you have to guess 1 first, then play n-1 game. It means that 1 divide the n into two parts: left part is empty while right part is 2-n.
  
  Then you guess 2; you also have two parts: 1 alone and 3-n.
4. so dp = k + max(dp_k_left, dp_k_right)
376 - Wiggle Subsequence

The difficult part is to create two dp arrays. Because for each number, you can combine it with the latter number to form the uptrending or the down trending.
377 - Combination Sum IV

Tricky to initialize the dp array.
392 - Is Subsequence

Maintain two pointer p and q, pointing to the first letter of the two strings and comparing the two letters. If same, move both pointer, otherwise, only move the pointer which points to the longer string.
413 - Arithmetic Slices

Misunderstanding part is: the sequence has to be continus. So the problem is simplified: check condition: A[i]-A[i-1] == A[i-1]-A[i-2], then we the new number can form arithmetic sequence with previous seq, so dp[i]=dp[i-1]. But these three number can be another arithmetic sequence, so dp[i]=dp[i-1]+1
416 - Partition Equal Subset Sum

It is hard to come up with the update rules. So the sum of the array must be oven; and the target is sum/2 so we need to find a subset to form such target. So the problem is like Q-377, given an array and target, find whether can form the target. But cannot iterate the target first then iterate the array, other the same number would be used multiple times. In this case, switch the order.
464 - Can I win

ref It is more related to dfs.
467 - Unique Substrings in Wraparound String

Hard to come up with the dp array and implementation.

First of all, substring means continus string.

Instead of basing on the input, the dp array is created based on each character in a,b,c,…,z, total length is 26. dp[i] means, say char[i] = ‘a’, number of different substrings with ‘a’ as the end.

If we have ‘abcd’, then substrings ending with ‘d’: d, cd, bcd, abcd, the numebr is 4, the lenghth of the subtring.

So the updating rule is: once we found the substring, which is p[i]-p[i-1]==1 or p[i-1]-p[i]==25, then k+=1; else k=1.
474 - Ones and Zeros

Similar 0-1backpacking. We create two dimensions array: dp(i,j) means using i zeros and j ones, the maximum strings we can choose. Then for each string, we have two choices: choose it, then dp[i,j]=dp[i-zeros, j-ones]+1.
494 - Target Sum

The idea is to split the numbers into two partitions: nums with ‘+’ and nums with ‘-‘.
We want find such partition that
sum(P) - sum(N) == target

sum(P) - sum(N) + sum(All) == target + sum(All)
sum(P) - sum(N) + sum(P) + sum(N) == target + sum(All)
sum(P) == (target + sum(All)) / 2
We know sum(P) is still integer. So if target + sum(All) is odd number, there is no such partition.
Otherwise, the problem becomes Partition Equal Subset Sum.
The time complexity is O(n2) and the space complexity is O(n).

Then it becomes the problem Q-416.
764 - Min Cost Climbing Stairs

Very similar to Q-198.

String

ASCII for Uppercase:65-90; Lowercase:97-122;number:48-57
string.punctuation 

mystr.rstrip('x') # remove 'x' from mystr
mystr.lower() # lower case
ord('a') = 97 | chr(97) = 'a'
s[::-1] # reverse the string

13 - Roman to Integer

If the value of current letter is greater than the previous one, deduct twice of the previous value.
14 - Longest Common Prefix

Instead of comparing each character of two strings, we maintain the variable of longest common prefix, and check whether such variable is same as the rest string, if so, great; otherwise, compare the common string with last charater lost, with the rest string.
20 - Valid Parentheses

Utilizing stack.
38 - Count and Say
67 - Add Binary
387 - First Unique Character in a String

Two times scan. First one is to count the frequency.
443 - String Compression
459 - Repeated Substring Pattern

First of all, repeated substring cannot be longer than half of the original string. So iterate the length of substrig from half to 1, check if it is the repeated substring.
521 - Longest Uncommon Subsequence I

If two strings are same, return false; otherwise, return the longer one.
541 - Reverse String II

For the substring with length 2k, reverse the first k string.
680 - Valid Palindrome II

Check the leftmost char and rightmost char, if they are not equal, then we can check the left middle substring: one without the left char and one without the right char. The substring should same to their inverse string.
686 - Repeated String Match

If B is a substring, then len(A)>=len(B) at least. Otherwise we repeat A until the condition is satisfied. If B is in A, return. Otherwise repeat A once in case of B=dabc While A=abcd.
696 - Count Binary Substrings

Given 001100, we need to find out the continuous 0 and 1, so we have (00, 11, 00). And for 00 and 11, they can for 2; for 11 and 00, they can form 2. So the total number is 4.
819 - Most Common Word

How to process the punctation is so complicated. The string should be splited by not only space but also the punctation. Example: ‘a, b,c,d, f’.
859 - Buddy Strings
893 - Groups of Special-Equivalent Strings

The sorted order of even-index substring an odd-index substring should be same for special strings.
917 - Reverse Only Letters
925 - Long Pressed Name

Iterate the strings and compare the length of same char.
929 - Unique Email Addresses

Tree

1. Consider when the input is None
2. When using recursive method to process tree problem, the step is:
    - how to stop the loop
    - recursive the process
3. max int = float('inf') / float('-inf') / sys.maxsize

104 - Maximum Depth of Binary Tree

First consider NONE case.
110 - Balanced Binary Tree

We need to ensure the current left and right tree is balanced, which means height dif is at most 1. At the same time, for left and right tree respectively, their left and right tree should also be balanced.

The aim of code is to compute the height of current node. But during the computation, we also need to keep trace whether the dif is greater than 1.
111 - Minimum Depth of Binary Tree

Basic problem - compute the path length, but when the root has only left tree but not right tree, the length should be 2 insted of 1.
226 - Invert Binary Tree

For each node, switch its left and right. For the given exmaple, by switching the last layer, we have (3,1,9,6). Then go to upper layer and switch, we have (9,6,3,1)
236 - Lowest Common Ancestor of a Binary Search Tree

Because it is a binary search tree, so we can know the position of p, q by comparing the value with root. Definitely we need to use recursion, the end condition is: when p, q are in the different sides of root, then return root. If root is one of p and q, return root. otherwise, recursive.
404 - Sum of Left Leaves

Split the problem into the subproblem: the sum of left leaves = value in left tree+ value in right tree. The stop condition is the current node has a left leave. But we still need to consider its right tree.
347 - Path Sum III

So tricky.
530 - Minimum Absolute Difference in BST

traverse the tree and get all values. Then compare.
538 - Convert BST to Greater Tree

Right-most traverse. But harder.
543 - Diameter of Binary Tree
563 - Binary Tree Tilt

So confused with the traversing. For each node, you need to get the sum of left and sum of right first, then you compute the dif. So, we need to traverse first, then process the root node.
669 - Trim a Binary Search Tree

DON’T ignore that it is a BST.
671 - Second Minimum Node In a Binary Tree

It is very tricky to get straight with the left, right tree subproblem.
687 - Longest Univalue Path

Path finding problem. There is a trap: for example, for a tree with all value being same, the longest univalue path is not the all_nodes-1, it should remove some subtree.

| | | | 1 | | | |
| :—: | :—: | :—: | :—: | :—: | :—: | :—: |
| | 1 | | | | 1 | |
| 1 | | 1 | | 1 | | 1 |

For the above example, the longest is 4.

For the answer, you can use both sides; but when you compute the each side, you can only use one side
993 - Cousins in Binary Tree

The traverse of tree. When you do traversing, it will not stop even you find the target. So in this case, you can use the self.target and update it when condition is satisfied.
1022 - Sum of Root To Leaf Binary Numbers

The traverse of tree. A little bit of tricky.