Нахождение минимальной стоимости для достижения конца массива

Question

Приведен массив затрат. Вы можете сделать два прыжка вперед или один прыжок назад. Если вы попадаете на определенный индекс, вам нужно добавить стоимость к общей сумме. Найдите минимальную стоимость, необходимую для пересечения массива или достижения конца массива.

Ввод:

5 (количество элементов в массиве)

[9,4,6,8,5] (Массив)

1 (Начальный индекс)

Вывод:

11

Как мы можем построить для этого DP-решение?

Answer 1

Вы можете использовать рекурсивную программу с Dp

//cur will the final destination that is last element at first execution
//N is no of elements
int Dp[N]={0};
Dp[0]=element[0]; //initial condition
least_path(cur,*elements,N)
{
   if(cur>N-1 || cur<0)
     return INT_MAX;
  if(Dp[cur])
   return Dp[cur];
  int temp1=least_path(cur-2,*elements,N)+element[cur];
  int temp2=least_path(cur+1,*elements,N)+element[cur];
  Dp[cur]=min(temp1,temp2);
  return Dp[cur];
}

Answer 2

Вы можете использовать алгоритм (график) Дейкстры для решения этой задачи.

Выполните следующие шаги:

1. Создать взвешенный ориентированный граф , соединив узел i-го индекса с узлами (i-1) th и (i + 2) th индекс с их стоимостью (если возможно).

2. Применить алгоритм Дейкстры к найти кратчайший маршрут между начальным узлом (индексом) и целью узел (индекс) .

Answer 3

Решение C ++ (dijikstras)

int minDist(vector<bool> &visited, vector<int> &dist, int n){
    int m = INT_MAX, res = 0;

    for(int i = 0; i < n; i++)
        if(!visited[i] && m > dist[i])
            m = dist[i], res = i;
    return res;
}

int minJump(int *arr, int n){
    vector<bool> visited(n, false);
    vector<int> dist(n, INT_MAX);

    dist[0] = 0;
    for(int c = 0; c < n - 1; c++){
        int u = minDist(visited, dist, n);
        visited[u] = true;

        if(u + 2 < n && !visited[u + 2] && dist[u] + arr[u + 2] < dist[u + 2])
            dist[u + 2] = dist[u] + arr[u + 2];
        if(u - 1 >= 0 && !visited[u - 1] && dist[u] + arr[u - 1] < dist[u - 1])
            dist[u - 1] = dist[u] + arr[u - 1];
    }
    return dist[n - 1];
}