Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

九、動態規劃 動態規劃程序設計是解決多階段決策過程最優化問題的⼀種途徑。動態規劃的設計⽅ 法對不同的問題,有各具特⾊的解題⽅法,⽽不存在⼀種萬能的動態規劃算法,可以…

  1. User

    九、動態規劃 動態規劃程序設計是解決多階段決策過程最優化問題的⼀種途徑。動態規劃的設計⽅ 法對不同的問題,有各具特⾊的解題⽅法,⽽不存在⼀種萬能的動態規劃算法,可以 解決各類最優化問題。需要滿⾜最優⼦結構和無後效性兩項基本條件。 動態規劃解決問題的步驟:

    1. 確定狀態:狀態是⼀個數學形式;
    2. 確定狀態轉移⽅程和邊界條件:遞歸或遞推;
    3. 程序實現。 動態規劃⼤致可以分為以下幾類:線性、區間、背包型、樹型、數位、狀態壓縮等。 常⾒問題有最⻑不下降序列、最⻑公共⼦序列出等。

    translate to english

  2. 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:

    1. Determine the states: A state is a mathematical representation;
    2. Determine the state transition equation and boundary conditions: recursion or iteration;
    3. 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.