To identify DP, we need to look at two things:

• Choice
• Making it optimal (min/max/largest)

At the core DP is enhanced recursion.

For finding the recurrance we do the following:

• Express the inputs as indexes
• Do all possibilites on those indexes
• Take optimal (best/longest/min/max) among them

We can always improve a recursive problem if there are possibility of it having sub-problems by using Memoization/Top-Down

• Create an empty memo array to store the results. Array would have dimensions equal to input indexes
• Every where we return the recursive result, we store in memo array
• We return early if the memo value exists, so we don't have to recompute it again

We can further improve the time complexity by completely removing the auxillary stack space by using Tabulation/Bottom-Up

• Copy base case
• Writing indexes in the opposite direction in for loops
• Copy recursion
• Sometimes, we might want to right shift the index such that 0 -> -1 and n -> n-1, so that base cases can be handled more easily

It can be further space optimized to using curr and prev 1D arrays.

Resources:

• Aditya Verma
• Striver
• Alvin