algorithm - 最小和使得每三个连续元素中的一个被取

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^th 数组元素与最后三个递归调用结果的最小值相加就可以得到大小为 i 的数组的正确答案？

Answer 1

递归公式确实是正确的，但前提是它被扩展为:

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

... 其中 n 是 arr 的大小.万一n < 3 , 那么输出是所有 arr 中的最小值当然是值(value)观。

递归公式满足“每3个连续元素中至少有一个元素被挑选”的要求，这等同于说两个之间的索引距离相邻的 picks(或数组的末尾)最多为 3:

• 对于 i>= 3，sum(i)将包括 i 处的值，以及至少 i-1、i-2 或 i-3 处的值之一，因为 sum其中每一个的定义也包括该索引处的值。显然，索引差异最多为 i - (i-3) , 即 3.

• 对于 i < 3，这是真的，因为它们前面的值少于 3 个。

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

• 作为sum(i)当必须包含 i 时最小化总和，即 sum(n-1), sum(n-2), sum(n-3) 中的最小值从而找到最优解。