九、動態規劃 動態規劃程序設計是解決多階段決策過程最優化問題的⼀種途徑。動態規劃的設計⽅ 法對不同的問題,有各具特⾊的解題⽅法,⽽不存在⼀種萬能的動態規劃算法,可以…
- User
九、動態規劃 動態規劃程序設計是解決多階段決策過程最優化問題的⼀種途徑。動態規劃的設計⽅ 法對不同的問題,有各具特⾊的解題⽅法,⽽不存在⼀種萬能的動態規劃算法,可以 解決各類最優化問題。需要滿⾜最優⼦結構和無後效性兩項基本條件。 動態規劃解決問題的步驟:
- 確定狀態:狀態是⼀個數學形式;
- 確定狀態轉移⽅程和邊界條件:遞歸或遞推;
- 程序實現。 動態規劃⼤致可以分為以下幾類:線性、區間、背包型、樹型、數位、狀態壓縮等。 常⾒問題有最⻑不下降序列、最⻑公共⼦序列出等。
translate to english
- Assistant
IX. Dynamic Programming
Dynamic programming programming is a method for solving multi-stage decision process optimization problems. The design methods of dynamic programming vary for different problems, each with its unique problem-solving approach, and there does not exist a universal dynamic programming algorithm that can solve all kinds of optimization problems. It needs to satisfy two basic conditions: optimal substructure and no aftereffect (i.e., the Markov property).
Steps to solve problems using dynamic programming:
- Determine the states: A state is a mathematical representation;
- Determine the state transition equation and boundary conditions: recursion or iteration;
- Implement the program.
Dynamic programming can be roughly divided into the following categories: linear, interval, knapsack type, tree structure, digit DP, state compression, etc.
Common problems include the longest non-decreasing sequence, the longest common subsequence, and so on.