Dynamic Programming
A problem-solving technique to solve complex problems by breaking them down into smaller, overlapping subproblems, solving each subproblem only once.
Each algorithm defines a state, transition, and base case to compute the solution.
Dynamic programming is recursion without repetition. The proper recursion is much important than memoization.
Whenever you write - or even think - the word "greeDY", your subconscious is telling you to use DYnamic programming.
How to Develop a DP algorithm
- Formulate the problem recursively
-
Specification: Describe the problem rather how to solve, but what the problem
-
Solution, give a formula for the problem in terms of the answers to smaller instances of exactly the same problem
-
Build solutions to your recurrence from the bottom up
-
identify the subproblems
- choose a memoization data structure
- identify dependency
- Find a good evalution order
- analyze space and running time
- write down the algoritm
Mechanical Recipe
- Subproblems
- Memoization Strucure
- Dependencies
- Evaluation Order
- Space and time
What DP mean
The programming is not code, but rather the older sense of planning or schedualing, typically by filling in a table.
动态规划步骤
-
Define the DP state
-
Formulate the recurrence relation
-
Iterate the DP values
-
Handle Edge Cases
-
Return