什么是動態(tài)規(guī)劃（Dynamic Programming）？動態(tài)規(guī)劃的意義是什么？

時間：2023-10-19 07:30:01 | 來源：網(wǎng)站運營

時間：2023-10-19 07:30:01 來源：網(wǎng)站運營

什么是動態(tài)規(guī)劃（Dynamic Programming）？動態(tài)規(guī)劃的意義是什么？：動態(tài)規(guī)劃中遞推式的求解方法不是動態(tài)規(guī)劃的本質(zhì)。

我曾經(jīng)作為省隊成員參加過NOI，保送之后也給學校參加NOIP的同學多次講過動態(tài)規(guī)劃，我試著講一下我理解的動態(tài)規(guī)劃，爭取深入淺出。希望你看了我的答案，能夠喜歡上動態(tài)規(guī)劃。

0. 動態(tài)規(guī)劃的本質(zhì)，是對問題狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程的定義。

引自維基百科

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

動態(tài)規(guī)劃是通過拆分問題，定義問題狀態(tài)和狀態(tài)之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決。

本題下的其他答案，大多都是在說遞推的求解方法，但如何拆分問題，才是動態(tài)規(guī)劃的核心。

而拆分問題，靠的就是狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程的定義。

1. 什么是狀態(tài)的定義？


首先想說大家千萬不要被下面的數(shù)學式嚇到，這里只涉及到了函數(shù)相關的知識。

我們先來看一個動態(tài)規(guī)劃的教學必備題：

給定一個數(shù)列，長度為N，
求這個數(shù)列的最長上升（遞增）子數(shù)列（LIS）的長度.
以
1 7 2 8 3 4
為例。
這個數(shù)列的最長遞增子數(shù)列是 1 2 3 4，長度為4；
次長的長度為3， 包括 1 7 8; 1 2 3 等.

要解決這個問題，我們首先要定義這個問題和這個問題的子問題。

有人可能會問了，題目都已經(jīng)在這了，我們還需定義這個問題嗎？需要，原因就是這個問題在字面上看，找不出子問題，而沒有子問題，這個題目就沒辦法解決。

所以我們來重新定義這個問題：

給定一個數(shù)列，長度為N，
設F_{k}為：以數(shù)列中第k項結(jié)尾的最長遞增子序列的長度.
求F_{1}..F_{N} 中的最大值.

顯然，這個新問題與原問題等價。

而對于F_{k}來講，F_{1} .. F_{k-1}都是F_{k}的子問題：因為以第k項結(jié)尾的最長遞增子序列（下稱LIS），包含著以第1..k-1中某項結(jié)尾的LIS。

上述的新問題F_{k}也可以叫做狀態(tài)，定義中的“F_{k}為數(shù)列中第k項結(jié)尾的LIS的長度”，就叫做對狀態(tài)的定義。

之所以把F_{k}做“狀態(tài)”而不是“問題” ，一是因為避免跟原問題中“問題”混淆，二是因為這個新問題是數(shù)學化定義的。


對狀態(tài)的定義只有一種嗎？當然不是。

我們甚至可以二維的，以完全不同的視角定義這個問題：

給定一個數(shù)列，長度為N，
設F_{i, k}為：
在前i項中的，長度為k的最長遞增子序列中，最后一位的最小值. 1/leq k/leq N.
若在前i項中，不存在長度為k的最長遞增子序列，則F_{i, k}為正無窮.
求最大的x，使得F_{N,x}不為正無窮。

這個新定義與原問題的等價性也不難證明，請讀者體會一下。

上述的F_{i, k}就是狀態(tài)，定義中的“F_{i, k}為：在前i項中，長度為k的最長遞增子序列中，最后一位的最小值”就是對狀態(tài)的定義。


2. 什么是狀態(tài)轉(zhuǎn)移方程？

上述狀態(tài)定義好之后，狀態(tài)和狀態(tài)之間的關系式，就叫做狀態(tài)轉(zhuǎn)移方程。

比如，對于LIS問題，我們的第一種定義：

設F_{k}為：以數(shù)列中第k項結(jié)尾的最長遞增子序列的長度.

設A為題中數(shù)列，狀態(tài)轉(zhuǎn)移方程為：

F_{1} = 1 （根據(jù)狀態(tài)定義導出邊界情況）
F_{k}=max(F_{i}+1 | A_{k}>A_{i}, i/in (1..k-1)) (k>1)

用文字解釋一下是：

以第k項結(jié)尾的LIS的長度是：保證第i項比第k項小的情況下，以第i項結(jié)尾的LIS長度加一的最大值，取遍i的所有值（i小于k）。

第二種定義：

設F_{i, k}為：在數(shù)列前i項中，長度為k的遞增子序列中，最后一位的最小值

設A為題中數(shù)列，狀態(tài)轉(zhuǎn)移方程為：

若A_{i}>F_{i-1,k-1}則F_{i,k}=min(A_{i},F_{i-1,k})
否則：F_{i,k}=F_{i-1,k}

（邊界情況需要分類討論較多，在此不列出，需要根據(jù)狀態(tài)定義導出邊界情況。）

大家套著定義讀一下公式就可以了，應該不難理解，就是有點繞。

這里可以看出，這里的狀態(tài)轉(zhuǎn)移方程，就是定義了問題和子問題之間的關系。

可以看出，狀態(tài)轉(zhuǎn)移方程就是帶有條件的遞推式。

3. 動態(tài)規(guī)劃迷思

本題下其他用戶的回答跟動態(tài)規(guī)劃都有或多或少的聯(lián)系，我也講一下與本答案的聯(lián)系。

a. “緩存”，“重疊子問題”，“記憶化”：

這三個名詞，都是在闡述遞推式求解的技巧。以Fibonacci數(shù)列為例，計算第100項的時候，需要計算第99項和98項；在計算第101項的時候，需要第100項和第99項，這時候你還需要重新計算第99項嗎？不需要，你只需要在第一次計算的時候把它記下來就可以了。

上述的需要再次計算的“第99項”，就叫“重疊子問題”。如果沒有計算過，就按照遞推式計算，如果計算過，直接使用，就像“緩存”一樣，這種方法，叫做“記憶化”，這是遞推式求解的技巧。這種技巧，通俗的說叫“花費空間來節(jié)省時間”。都不是動態(tài)規(guī)劃的本質(zhì)，不是動態(tài)規(guī)劃的核心。

b. “遞歸”：

遞歸是遞推式求解的方法，連技巧都算不上。

c. "無后效性"，“最優(yōu)子結(jié)構(gòu)”：

上述的狀態(tài)轉(zhuǎn)移方程中，等式右邊不會用到下標大于左邊i或者k的值，這是"無后效性"的通俗上的數(shù)學定義，符合這種定義的狀態(tài)定義，我們可以說它具有“最優(yōu)子結(jié)構(gòu)”的性質(zhì)，在動態(tài)規(guī)劃中我們要做的，就是找到這種“最優(yōu)子結(jié)構(gòu)”。

在對狀態(tài)和狀態(tài)轉(zhuǎn)移方程的定義過程中，滿足“最優(yōu)子結(jié)構(gòu)”是一個隱含的條件（否則根本定義不出來）。對狀態(tài)和“最優(yōu)子結(jié)構(gòu)”的關系的進一步解釋，什么是動態(tài)規(guī)劃？動態(tài)規(guī)劃的意義是什么？ - 王勐的回答 寫的很好，大家可以去讀一下。

需要注意的是，一個問題可能有多種不同的狀態(tài)定義和狀態(tài)轉(zhuǎn)移方程定義，存在一個有后效性的定義，不代表該問題不適用動態(tài)規(guī)劃。這也是其他幾個答案中出現(xiàn)的邏輯誤區(qū)：

動態(tài)規(guī)劃方法要尋找符合“最優(yōu)子結(jié)構(gòu)“的狀態(tài)和狀態(tài)轉(zhuǎn)移方程的定義，在找到之后，這個問題就可以以“記憶化地求解遞推式”的方法來解決。而尋找到的定義，才是動態(tài)規(guī)劃的本質(zhì)。

有位答主說：

分治在求解每個子問題的時候，都要進行一遍計算
動態(tài)規(guī)劃則存儲了子問題的結(jié)果，查表時間為常數(shù)

這就像說多加辣椒的菜就叫川菜，多加醬油的菜就叫魯菜一樣，是存在誤解的。

文藝的說，動態(tài)規(guī)劃是尋找一種對問題的觀察角度，讓問題能夠以遞推（或者說分治）的方式去解決。尋找看問題的角度，才是動態(tài)規(guī)劃中最耀眼的寶石?。ù箪F）