Dynamic programming problem characteristics
- count
- How many ways are there to get to the bottom right
- How many ways can I pick the sum of k numbers
- Find the maximum and minimum
- The maximum numeric sum of the path from the upper left corner to the lower right corner
- Maximum ascending subsequence length
- Beg existence
- Stone game, whether the first hand will win
- Can we pick k numbers such that the sum is sum
Dynamic programming problem solving steps
- Determine the state of
- The last step in studying the optimal strategy
- Subproblem
- Transfer equation
- We get it directly from the subproblem definition
- Initial conditions and boundary cases
- thoughtful
- Calculate the order
- So let’s use what we did before
Common types of dynamic planning
- Coordinates type
- Sequence type
- Divide the type
- Interval type
- Backpack type
- Longest sequence type
- Game type
- comprehensive