Smallest cost traversal of an array

152 views Asked by At

How do you compute the smallest cost traversal of an integer array using steps and jumps, while also counting the first and last element of the array? A step is moving to the next immediate value in the array e.g. array[currentIndex + 1], and a jump is moving two spots e.g. array[currentIndex + 2]. I have the following function which I want to return the minimum sum started, it adds the first and last elements to the sum, but I'm stuck on the middle values of the array.

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

There are 2 answers

1
Glorfindel On BEST ANSWER

You can try this:

    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];
    }
1
Rick Davin On

One possible solution:

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

This allows for step to be a parameter. Maybe now you want to step either 1 or 2 away from the start. Maybe later you want to step 5 spots away.