理解动态规划中的状态

我们来举个例子来讨论一下。从 ñ 物品，你可以有多少种选择 [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

确定状态是动态规划中最重要的部分之一。它由定义我们问题的参数数量和优化计算组成，我们可以优化整个问题。