给定一个包含 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))
请解释所形成的递归方程背后的直觉。为什么将当前第 ith 数组元素与最后三个递归调用结果的最小值相加就可以得到大小为 i 的数组的正确答案?
最佳答案
递归公式确实是正确的,但前提是它被扩展为:
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)
中的最小值从而找到最优解。
关于algorithm - 最小和使得每三个连续元素中的一个被取,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45462667/