Algorithm - Dynamic Programming
Algorithm - Dynamic Programming
What is Dynamic Programming?
Principle of Optimality (Bellman, 1957):
An optimal sequence of decisions has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal decision with regard to the state resulting from the first decision.
The Other Algorithmic Design Philosophy
Divide-and-Conquer:
The problem is divided and the subproblems are processed in a recursive manner, but the solutions of Divide-and-Conquer subproblems are usually not repeated, and when they are repeated, the same subproblems are usually recalculated.Greedy Approach:
At each stage, starting from a certain starting point, each input is checked one by one to see if it is suitable to be added to the answer. If it is not possible to find a selection procedure to check one by one for the optimization problem to be handled, we will discuss it later.
Divide and Conquer and Dynamic Programming are very similar. The difference is that Dynamic Programming’s subproblems have many overlaps, which can be stored in a table without recalculation, exchanging space for time.
