Наименьшая стоимость обхода массива

Question

Как вы вычисляете наименьший обход стоимости целочисленного массива с помощью шагов и переходов, а также подсчитываете первый и последний элементы массива? Шаг переходит к следующему непосредственному значению в массиве, например. 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; 
} 

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

Это позволяет шаг, чтобы быть параметром. Возможно, теперь вы хотите сделать шаг 1 или 2 от начала. Может быть, позже вы захотите сделать 5 пятен.