-1

我被问到这个面试问题，我完全懵了。各位大佬怎么解决的：

从数组的开头到结尾，以最小化您登陆的元素总和的方式。

  1. 您可以移动到下一个元素，即从索引 1 转到索引 2。
  2. 或者你可以跳过一个元素。即从索引 1 到索引 3。
4

3 回答 3

2

假设你只从左到右移动，并且你想找到一种方法从一个元素数组的索引0到索引，这样你走的路径的总和是最小的。从 index ，您只能前进到 index或 index 。n - 1nii + 1i + 2

观察从 index 到 index 的最小路径是从 index 到 index 的最小路径与从 index0到 index的最小k路径之间的最小值。根本没有其他途径可走。0k - 10k- 2

因此，我们可以有一个动态规划的解决方案：

DP[0] = A[0]
DP[1] = A[0] + A[1]
DP[k] = min(DP[0], DP[1]) + A[k]

A是元素的数组。数组将存储从 index
DP到达 index 处元素的最小总和。i0

结果将在DP[n - 1].

于 2013-04-26T16:08:51.857 回答
0

这似乎是动态编程解决方案的理想场所。

跟踪两个值，奇数/偶数。
我们将Even表示我们使用了以前的值，并Odd表示我们没有。

int Even = 0; int Odd = 0;
int length = arr.length;

从后面开始。我们可以取或不取号码。所以： 

Even = arr[length];  
Odd = 0;`

现在我们用两个案例移动到下一个元素。要么我们是偶数，在这种情况下，我们可以选择获取元素或跳过它。或者我们很奇怪，不得不接受这个元素。 

int current = arr[length - 1]
Even = Min(Even + current, Odd + current);
Odd = Even;

我们可以对此进行循环并实现 O(n) 解决方案！

于 2013-04-26T16:03:00.880 回答
0

爪哇：

static int getMinSum(int elements[])
{
    if (elements == null || elements.length == 0)
    {
        throw new IllegalArgumentException("No elements");
    }
    if (elements.length == 1)
    {
        return elements[0];
    }
    int minSum[] = new int[elements.length];
    minSum[0] = elements[0];
    minSum[1] = elements[0] + elements[1];
    for (int i = 2; i < elements.length; i++)
    {
        minSum[i] = Math.min(minSum[i - 1] + elements[i], minSum[i - 2] + elements[i]);
    }
    return Math.min(minSum[elements.length - 2], minSum[elements.length - 1]);
}

输入：

int elements[] = { 1, -2, 3 };
System.out.println(getMinSum(elements));

输出：

-1

案例描述：

我们从索引 0 开始。我们必须取 1。现在我们可以去索引 1 或 2。因为 -2 很有吸引力，所以我们选择它。现在我们可以去索引 2 或跳它。更好的跳跃，我们的和是最小的 1 + (-2) = -1。

另一个例子（伪代码）：

getMinSum({1, 1, 10, 1}) == 3
getMinSum({1, 1, 10, 100, 1000}) == 102

算法：

O(n) 复杂度。动态规划。我们从左到右填充 minSum 数组。不变量：minSum[i] = min(minSum[i - 1] + elements[i] /* move by 1 */ , minSum[i - 2] + elements[i] /* hop */ ).

于 2013-04-26T16:36:46.460 回答