使每三个连续元素中取一个的最小和

Question

给定一个由n个非负整数组成的数组(ARR[])，我们必须找到元素的最小和，以便每3个连续元素中至少有一个被选中。

Input : arr[] = {1, 2, 3}
Output : 1

Input : arr[] = {1, 2, 3, 6, 7, 1}
Output : 4
We pick 3 and 1  (3 + 1 = 4)
Note that there are following subarrays
of three consecutive elements
{1, 2, 3}, {2, 3, 6}, {3, 6, 7} and {6, 7, 1}
We have picked one element from every subarray.

Input : arr[] = {1, 2, 3, 6, 7, 1, 8, 6, 2,
                 7, 7, 1}
Output : 7
The result is obtained as sum of 3 + 1 + 2 + 1

sum[i]= arr[i] + min(sum[i-1],sum[i-2],sum[i-3])
where the base condition is: 
if i==3, then sum(3)= arr[3] + min(sum(0),sum(1),sum(2)) where 
    sum(0)=arr[0]
    sum(1)=arr[1]
    sum(2)=arr[2]
result=min(sum(n-1), sum(n-2), sum(n-3))

请解释所形成的递归方程背后的直觉。为什么添加当前的第i个^第数组元素和最后三次递归调用的结果的最小值会给出大小为i的数组的正确答案呢？

Answer 1

递归公式确实是正确的，但前提是用以下方法扩展它：

output = min(sum(n-1), sum(n-2), sum(n-3))

...其中n是arr的大小。如果n<3，则输出是所有arr值中的最小值。

递归公式满足了“每连续3个元素中至少有一个被拾取”的要求，这与说两个相邻拾取（或数组末尾）之间的索引距离最多为3：

递归公式（包括最终输出的必要公式）也满足了输出“最小元素和”的要求。这是因为最优解必须包含指数n-1、n-2或n-3处的值，否则不满足其他条件。

• 由于sum(i)在必须包含i时使和最小，因此sum(n-1)、sum(n-2)、sum(n-3)中的最小值将找到最优解。