Abstract
- Divide a given problems into smaller problems, answers to those smaller problems generate the answer to the given problem. We remember the answers to those smaller problems, so we don’t re-solve those smaller problems
- 3 key components - Overlapping Subproblems (重复子问题), Optimal Substructure ( 最优子结构) & Statelessness (无后效性)
Debugging
Print out DP Table to check any errors
Question Bank
Basics
Continuous Sub-sequence
- 628B - New Skateboard (Number Theory Required)
Simulation
DP Problem Properties
Overlapping Subproblems (重复子问题)
- Occur when a problem can be broken down into smaller subproblems that are solved repeatedly
- We can store the solutions to the subproblems as we solve them. This allows us to avoid re-solving the subproblems when we encounter them again
Optimal Substructure (最优子结构)
- Answer to a given problem has to be a Combination of the optimal solution of its smaller problems - solve the smaller problems in the best way possible, we solve the given problem (如果原问题的最优解可以从子问题的最优解构建得来，则它就具有最优子结构)
- When a problem has optimal substructure, we can use the solutions to the subproblems to construct the solution to the original problem
Knapsack Problem
The solution can be found by combining the optimal solutions to the knapsack problem with smaller weights and values.
Statelessness (无后效性)
- Solutions to smaller problems are deterministic
- 给定一个确定的状态， 其未来发展只与该状态有关， 与该状态所经历的过去的所有状态无关
- 如果未来发展与该状态和该状态的前一个状态相关，我们可以靠矩阵来解。但如果回溯的状态过多，就难了
- 许多Backtracking problems 都不具有无后效性， 无法使用 Dynamic Programming 快速求解
DP Tools
DP Table
- Trade space for time
- Use extra space to hold intermediate results to avoid duplicated computation
- A mapping between the State and the correspnding solution to each sub-problems at that particular State
- Can take the form of Array or simply a variable