Leetcode-Dynamic Programming

DP could be applied, only if the main problem can be divided into overlapping subproblems that can be solved independently.

For using dynamic programming to solve problem, there are 3 steps to think about:

Step0 . To recognize it might be a DP problem and describe brute force solution verbally during the interview.

Step1. Think about what’s base case.

Step2. Think about how do we formulate core idea into recursive formulation mathematically usually by observing relationship between current subproblem and previous subproblem.

Step3. Think about how to return our target from our memorization table usually by taking the last cell in memorization table as our target.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store