理解動態規劃中的狀態

我們來舉個例子來討論一下。從 ñ 物品，你可以有多少種選擇 [R 專案？你知道它表示 。現在想想一個單項。

• 如果你沒有選擇該專案，那麼你必須從剩餘的 n-1 專案中獲取 r 專案，該專案由。 ****
• 如果你選擇該專案，則必須從剩餘的 n-1 專案中獲取 r -1 專案，該專案由 。

這兩者的總和給出了我們總的方式。那是：

如果我們認為 nCr(n,r) 是一個以 n 和 r 為引數並確定的函式 ，我們可以將上面提到的關係寫成：

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

這是一種遞迴關係。要終止它，我們需要確定基本情況。我們知道， 和 。使用這兩個作為基本情況，我們的演算法確定 將是：

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

如果我們以圖形方式檢視過程，我們可以看到一些遞迴被多次呼叫。例如：如果我們取 n = 8 且 r = 5 ，我們得到：

https://i.stack.imgur.com/DQatV.jpg

我們可以通過使用陣列 dp 來避免這種重複呼叫。由於有 2 個引數，我們需要一個 2D 陣列。我們將使用 -1 初始化 dp 陣列，其中 -1 表示尚未計算的值。我們的程式將是： **** ****

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

為了確定 ，我們需要兩個引數 n 和 r 。這些引數稱為狀態。我們可以簡單地推斷出狀態的數量決定了 dp 陣列的維數。陣列的大小將根據我們的需要而改變。我們的動態程式設計演算法將保持以下一般模式：

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

確定狀態是動態規劃中最重要的部分之一。它由定義我們問題的引數數量和優化計算組成，我們可以優化整個問題。