数组的最小代价遍历

Question

如何使用步长和跳转计算整数数组的最小成本遍历，同时计算数组的第一个和最后一个元素？一个步骤是移动到数组中的下一个立即值，例如array[currentIndex + 1]，跳转移动两个点，例如数组 [当前索引 + 2]。我有以下函数，我想要 return 最小和开始，它将第一个和最后一个元素添加到总和，但我被困在数组的中间值上。

An example of this would be {2, 10, 4, 14, 44, 28, 16, 18} -> 66
which would add indexes 0, 2, 3, 5, and 7.

====

public int Cost(int[] board)
{
    int sum = board[0];
    int index = 0;
    while (index < board.Length)
    {
        //Add the final array value to the sum
        if (index + 1 == board.length)
        {
            sum += board[index];
            break;
        }
        //Add other values here

        index++;
    }
    return sum;
}

Answer 1

你可以试试这个：

    public int Cost(int[] board)
    {
        int[] cost = new int[board.Length];
        for (int i = 0; i < board.Length; i++) {
            if (i == 0) {
                cost[i] = board[0];
            } else if (i == 1) {
                cost[i] = board[1] + cost[0];
            } else {
                cost[i] = board[i] + Math.Min(cost[i - 1], cost[i - 2]);
            }
        }
        return cost[board.Length - 1];
    }

Answer 2

一个可能的解决方案：

public int Cost(int[] board, int step = 1)
{
    if (board == null) return -1;
    if (board.Length == 0) return 0;

    // always add first and last index (if its not the first)
    int sum = board[0];

    if (board.Length > 1) sum += board[board.Length - 1];

    // assumes step is > 0
    for (int i = step; i < (board.Length - 1); i += step)
    {
        sum += board[i];
    }

    return sum;
}

这允许将 step 作为参数。也许现在您想从一开始就走 1 步或 2 步。也许稍后你想离开 5 个位置。

数组的最小代价遍历

Smallest cost traversal of an array

c#

arrays

traversal