最小代价遍历数组

本文关键字：数组 遍历 代价 | 更新日期: 2023-09-27 17:54:15

如何使用步进和跳跃计算整数数组的最小遍历成本，同时还计算数组的第一个和最后一个元素?一步是移动到数组中的下一个直接值，例如array[currentIndex + 1]，跳跃是移动两个点，例如array[currentIndex + 2]。我有下面的函数，我想返回最小和开始，它将第一个和最后一个元素添加到和，但我被困在数组的中间值。

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;
}

最小代价遍历数组

你可以试试:

    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];
    }

一个可能的解决方案:

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个点远。

相关文章：