Dada una array arr[] de tamaño N y un número entero K , uno puede pasar de un índice i a cualquier otro índice j tal que j ≤ i+k . El costo de estar en cualquier índice ‘ i ‘ es arr[i] . La tarea es encontrar el costo mínimo para llegar al final de la array a partir del índice 0 .
Ejemplos :
Entrada: arr[] = {2, 4, 1, 6, 3}, K = 2
Salida: 6
Explicación: La ruta se puede tomar como 2 -> 1-> 3 = 6Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Salida: 10
Explicación: La ruta se puede tomar como 1->3->6 = 10
Enfoque ingenuo : la tarea se puede resolver mediante programación dinámica . Mantenga una array dp[] donde, donde dp[i] indica el costo mínimo requerido para alcanzar el i-ésimo índice. Siga los pasos a continuación para resolver el problema:
- Recorra todos los elementos K hacia atrás desde el elemento actual , encuentre el valor mínimo de dp y agréguelo a la respuesta actual.
- Entonces, calcular la respuesta para el i-ésimo índice será dp[i] = arr[i] + min(dp[j] para todos los j tales que ik <= j < i ) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum jumps
int solve(vector<int>& arr, int K)
{
int size = arr.size();
vector<int> dp(size, 0);
// Initially only a single element
dp[0] = arr[0];
for (int idx = 1; idx < size; idx++) {
// At most k elements backwards
int end = max(-1, idx - K - 1);
int mini = INT_MAX;
// Find minimum among all the values
for (int ptr = idx - 1; ptr > end; ptr--) {
mini = min(mini, dp[ptr]);
}
dp[idx] = arr[idx] + mini;
}
// Return cost to reach the
// last index of array
return dp[size - 1];
}
// Driver Code
int main()
{
vector<int> arr = { 2, 4, 1, 6, 3 };
int K = 2;
int ans = solve(arr, K);
cout << ans << "\n";
}
// This code is contributed by Taranpreet
Java
// Java program for the above approach
class GFG {
// Function to find the minimum jumps
static int solve(int[] arr, int K) {
int size = arr.length;
int[] dp = new int[size];
for (int i = 0; i < size; i++) {
dp[i] = 0;
}
// Initially only a single element
dp[0] = arr[0];
for (int idx = 1; idx < size; idx++) {
// At most k elements backwards
int end = Math.max(-1, idx - K - 1);
int mini = Integer.MAX_VALUE;
// Find minimum among all the values
for (int ptr = idx - 1; ptr > end; ptr--) {
mini = Math.min(mini, dp[ptr]);
}
dp[idx] = arr[idx] + mini;
}
// Return cost to reach the
// last index of array
return dp[size - 1];
}
// Driver Code
public static void main(String args[]) {
int[] arr = { 2, 4, 1, 6, 3 };
int K = 2;
int ans = solve(arr, K);
System.out.println(ans);
}
}
// This code is contributed by Saurabh Jaiswal
Python3
# Python program for the above approach
# Function to find the minimum jumps
def solve(arr, K):
size = len(arr)
dp = [0] * (size)
# Initially only a single element
dp[0] = arr[0]
for idx in range(1, size, 1):
# At most k elements backwards
end = max(-1, idx - K - 1)
mini = float('inf')
# Find minimum among all the values
for ptr in range(idx - 1, end, -1):
mini = min(mini, dp[ptr])
dp[idx] = arr[idx] + mini
# Return cost to reach the
# last index of array
return (dp[-1])
# Driver Code
if __name__ == "__main__":
arr = [2, 4, 1, 6, 3]
K = 2
ans = solve(arr, K)
print(ans)
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the minimum jumps
static int solve(int []arr, int K)
{
int size = arr.Length;
int []dp = new int[size];
for(int i = 0; i < size; i++) {
dp[i] = 0;
}
// Initially only a single element
dp[0] = arr[0];
for (int idx = 1; idx < size; idx++) {
// At most k elements backwards
int end = Math.Max(-1, idx - K - 1);
int mini = Int32.MaxValue;
// Find minimum among all the values
for (int ptr = idx - 1; ptr > end; ptr--) {
mini = Math.Min(mini, dp[ptr]);
}
dp[idx] = arr[idx] + mini;
}
// Return cost to reach the
// last index of array
return dp[size - 1];
}
// Driver Code
public static void Main()
{
int []arr = { 2, 4, 1, 6, 3 };
int K = 2;
int ans = solve(arr, K);
Console.WriteLine(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the minimum jumps
function solve(arr, K) {
let size = arr.length
let dp = new Array(size + 1).fill(0)
// Initially only a single element
dp[0] = arr[0]
for (let idx = 1; idx < size; idx++) {
// At most k elements backwards
let end = Math.max(-1, idx - K - 1)
let mini = Number.MAX_VALUE
// Find minimum among all the values
for (let ptr = idx - 1; ptr > end; ptr--)
mini = Math.min(mini, dp[ptr])
dp[idx] = arr[idx] + mini
}
// Return cost to reach the
// last index of array
return dp[size - 1]
}
// Driver Code
let arr = [2, 4, 1, 6, 3]
let K = 2
ans = solve(arr, K)
document.write(ans)
// This code is contributed by Potta Lokesh
</script>
Producción:
6
Complejidad temporal : O(N * K)
Espacio auxiliar : O(N)
Enfoque eficiente : en lugar de calcular el costo mínimo para cada índice , utilice el enfoque de ventana deslizante . Utilice la ventana deslizante de tamaño K , de modo que el elemento mínimo siempre esté presente en el frente y se mantenga el orden ordenado . Siga los pasos a continuación para resolver el problema:
- Inicialice deque para contener los datos, ya que admite la operación eficiente de elementos emergentes tanto desde el frente como desde la parte posterior.
- Inserte el primer elemento junto con su índice en el deque. El índice también se inserta para rastrear si algún elemento está dentro del límite de ventana de tamaño K .
- Luego, comience a recorrer desde el índice 1 hasta el final de la array. Para cada índice, elimine todos los elementos del frente que estén fuera del tamaño de ventana actual, es decir, diferencia entre índices > k.
- Calcule current_value como la suma de arr[i] y el primer valor de dequeue . Aquí se agrega el primer valor, porque es el valor más pequeño en la ventana actual.
- Luego, extraiga todos los elementos de la parte posterior de deque que tengan un valor mayor o igual que current_value. Esto se hace para mantener un orden ordenado en el deque.
- Finalmente, devuelva el último valor en el deque, mostrando el costo para alcanzar el último índice de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum jumps
int solve(int arr[], int K, int size)
{
deque<pair<int, int> > ququ;
// Insert index and value
ququ.push_back({ 0, arr[0] });
for (int i = 1; i < size; i++) {
// Remove elements from front
// which are out of curr_window size
while ((ququ.size() > 0)
&& ((i - ququ.front().first) > K))
ququ.pop_front();
int curr_val = arr[i] + ququ.front().second;
// Pop greater elements from back
while ((ququ.size() > 0)
&& (curr_val <= ququ.back().second))
ququ.pop_back();
// Append index and curr_val
ququ.push_back({ i, curr_val });
}
// Finally return last value
// indicating cost to reach the last index
return ququ.back().second;
}
// driver code
int main()
{
int arr[] = { 2, 4, 1, 6, 3 };
int K = 2;
int size = sizeof(arr) / sizeof(arr[0]);
int ans = solve(arr, K, size);
cout << ans << endl;
return 0;
}
// This code is contributed by Palak Gupta
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
// Function to find the minimum jumps
public static int solve(int arr[], int K, int size)
{
Deque<pair> ququ = new LinkedList<pair>();
// Insert index and value
ququ.addLast(new pair(0, arr[0]));
for (int i = 1 ; i < size ; i++) {
// Remove elements from front
// which are out of curr_window size
while ((ququ.size() > 0) && ((i - ququ.getFirst().x) > K))
ququ.removeFirst();
int curr_val = arr[i] + ququ.getFirst().y;
// Pop greater elements from back
while ((ququ.size() > 0) && (curr_val <= ququ.getLast().y))
ququ.removeLast();
// Append index and curr_val
ququ.addLast(new pair(i, curr_val));
}
// Finally return last value
// indicating cost to reach the last index
return ququ.getLast().y;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 4, 1, 6, 3 };
int K = 2;
int size = arr.length;
int ans = solve(arr, K, size);
System.out.println(ans);
}
}
class pair{
Integer x;
Integer y;
pair(int a,int b){
this.x = a;
this.y = b;
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python program for the above approach from collections import deque # Function to find the minimum jumps def solve(arr, K): size = len(arr) ququ = deque() # Insert index and value ququ.append((0, arr[0])) for i in range(1, size, 1): # Remove elements from front # which are out of curr_window size while(ququ and i - ququ[0][0] > K): ququ.popleft() curr_val = arr[i] + ququ[0][1] # Pop greater elements from back while(ququ and curr_val <= ququ[-1][1]): ququ.pop() # Append index and curr_val ququ.append((i, curr_val)) # Finally return last value # indicating cost to reach the last index return ququ[-1][1] # Driver Code if __name__ == "__main__": arr = [2, 4, 1, 6, 3] K = 2 ans = solve(arr, K) print(ans)
Producción
6
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)