导出动态规划的递归公式

Question

我现在正试图解决一个家庭作业问题，我有点难倒了。

问题是从一个整数数组中挑选元素相加得到最大的和，但是三个连续的元素不能被挑选在一起。

S(i)是可能的最大和，数组中的每个元素用A[0…i]表示。

首先，我需要提出S(I)的递归公式，包括基本情况。

我提出了基本情况，但老实说，我不确定它们是否完全正确:

S(0) = max(0, A[0])
S(1) = max(S(0), A[1], A[0]+A[1])
S(2) = max(S1, A[0]+A[2], A[1]+A[2])

我的递归公式将是:

max(0, S(i-1), S(i-2) + A[i], S(i-3) + A[i] + A[i-1])

至少我在正确的轨道上吗?

Answer 1

元素0..I(对于I>2)必须被以下三种情况中的一种所覆盖:

• 不包含A(i)
• 包括A(i)但不包括A(i-1)
• 包括A(i)和A(i-1)，但不包括A(i-2)。

因此,S (i) = max (S(张),(我)+ S(我),(我)+(张)+ S(我))

基本情况可以通过定义A(k)=S(k)=0来处理所有k<0并重用相同的关系。