Dada una array arr[] de N enteros y un entero K , uno puede pasar de un índice i a cualquier otro j si j ≤ i + k . El costo de pasar de un índice i al otro índice j es abs(arr[i] – arr[j]) . Inicialmente, comenzamos desde el índice 0 y necesitamos alcanzar el último índice, es decir , N – 1 . La tarea es llegar al último índice en el mínimo costo posible.
Ejemplos:
Entrada: arr[] = {10, 30, 40, 50, 20}, k = 3
Salida: 30
0 -> 1 -> 4
el costo total será: |10-30| + |30-20| = 30
Entrada: arr[] = {40, 10, 20, 70, 80, 10}, k = 4
Salida: 30
Enfoque 1: El problema se puede resolver usando Programación Dinámica. Partimos del índice 0 y podemos visitar cualquiera de los índices desde i+1 hasta i+k, por lo que el coste mínimo de todos los caminos se almacenará en dp[i]. Una vez lleguemos a la N-1, será nuestro caso base. Use la memorización para memorizar los estados, de modo que no necesitemos volver a visitar el estado nuevamente para reducir la complejidad.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum cost
// to reach the last index
int FindMinimumCost(int ind, int a[],
int n, int k, int dp[])
{
// If we reach the last index
if (ind == (n - 1))
return 0;
// Already visited state
else if (dp[ind] != -1)
return dp[ind];
else {
// Initially maximum
int ans = INT_MAX;
// Visit all possible reachable index
for (int i = 1; i <= k; i++) {
// If inside range
if (ind + i < n)
ans = min(ans, abs(a[ind + i] - a[ind])
+ FindMinimumCost(ind + i, a,
n, k, dp));
// We cannot move any further
else
break;
}
// Memoize
return dp[ind] = ans;
}
}
// Driver Code
int main()
{
int a[] = { 10, 30, 40, 50, 20 };
int k = 3;
int n = sizeof(a) / sizeof(a[0]);
int dp[n];
memset(dp, -1, sizeof dp);
cout << FindMinimumCost(0, a, n, k, dp);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GfG
{
// Function to return the minimum cost
// to reach the last index
static int FindMinimumCost(int ind, int a[],
int n, int k, int dp[])
{
// If we reach the last index
if (ind == (n - 1))
return 0;
// Already visited state
else if (dp[ind] != -1)
return dp[ind];
else {
// Initially maximum
int ans = Integer.MAX_VALUE;
// Visit all possible reachable index
for (int i = 1; i <= k; i++)
{
// If inside range
if (ind + i < n)
ans = Math.min(ans, Math.abs(a[ind + i] - a[ind]) +
FindMinimumCost(ind + i, a, n, k, dp));
// We cannot move any further
else
break;
}
// Memoize
return dp[ind] = ans;
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 10, 30, 40, 50, 20 };
int k = 3;
int n = a.length;
int dp[] = new int[n];
Arrays.fill(dp, -1);
System.out.println(FindMinimumCost(0, a, n, k, dp));
}
}
// This code is contributed by Prerna Saini
Python3
# Python 3 implementation of the approach import sys # Function to return the minimum cost # to reach the last index def FindMinimumCost(ind, a, n, k, dp): # If we reach the last index if (ind == (n - 1)): return 0 # Already visited state elif (dp[ind] != -1): return dp[ind] else: # Initially maximum ans = sys.maxsize # Visit all possible reachable index for i in range(1, k + 1): # If inside range if (ind + i < n): ans = min(ans, abs(a[ind + i] - a[ind]) + FindMinimumCost(ind + i, a, n, k, dp)) # We cannot move any further else: break # Memoize dp[ind] = ans return ans # Driver Code if __name__ == '__main__': a = [10, 30, 40, 50, 20] k = 3 n = len(a) dp = [-1 for i in range(n)] print(FindMinimumCost(0, a, n, k, dp)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the above approach
using System;
class GfG
{
// Function to return the minimum cost
// to reach the last index
static int FindMinimumCost(int ind, int []a,
int n, int k, int []dp)
{
// If we reach the last index
if (ind == (n - 1))
return 0;
// Already visited state
else if (dp[ind] != -1)
return dp[ind];
else {
// Initially maximum
int ans = int.MaxValue;
// Visit all possible reachable index
for (int i = 1; i <= k; i++)
{
// If inside range
if (ind + i < n)
ans = Math.Min(ans, Math.Abs(a[ind + i] - a[ind]) +
FindMinimumCost(ind + i, a, n, k, dp));
// We cannot move any further
else
break;
}
// Memoize
return dp[ind] = ans;
}
}
// Driver Code
public static void Main()
{
int []a = { 10, 30, 40, 50, 20 };
int k = 3;
int n = a.Length;
int []dp = new int[n];
for(int i = 0; i < n ; i++)
dp[i] = -1 ;
Console.WriteLine(FindMinimumCost(0, a, n, k, dp));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return the minimum cost
// to reach the last index
function FindMinimumCost($ind, $a, $n, $k, $dp)
{
// If we reach the last index
if ($ind == ($n - 1))
return 0;
// Already visited state
else if ($dp[$ind] != -1)
return $dp[$ind];
else
{
// Initially maximum
$ans = PHP_INT_MAX;
// Visit all possible reachable index
for ($i = 1; $i <= $k; $i++)
{
// If inside range
if ($ind + $i < $n)
$ans = min($ans, abs($a[$ind + $i] - $a[$ind]) +
FindMinimumCost($ind + $i, $a, $n, $k, $dp));
// We cannot move any further
else
break;
}
// Memoize
return $dp[$ind] = $ans;
}
}
// Driver Code
$a = array(10, 30, 40, 50, 20 );
$k = 3;
$n = sizeof($a);
$dp = array();
$dp = array_fill(0, $n, -1);
echo(FindMinimumCost(0, $a, $n, $k, $dp));
// This code is contributed by Code_Mech.
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the minimum cost
// to reach the last index
function FindMinimumCost(ind , a , n , k , dp) {
// If we reach the last index
if (ind == (n - 1))
return 0;
// Already visited state
else if (dp[ind] != -1)
return dp[ind];
else {
// Initially maximum
var ans = Number.MAX_VALUE;
// Visit all possible reachable index
for (var i = 1; i <= k; i++) {
// If inside range
if (ind + i < n)
ans = Math.min(ans, Math.abs(a[ind + i] - a[ind])
+ FindMinimumCost(ind + i, a, n, k, dp));
// We cannot move any further
else
break;
}
// Memoize
return dp[ind] = ans;
}
}
// Driver Code
var a = [ 10, 30, 40, 50, 20];
var k = 3;
var n = a.length;
var dp = Array(n).fill(-1);
document.write(FindMinimumCost(0, a, n, k, dp));
// This code contributed by aashish1995
</script>
Producción:
30
Complejidad de tiempo: O(N * K)
Espacio auxiliar: O(N)
Enfoque 2:
El segundo enfoque también requiere el uso de programación dinámica. Este enfoque se basa en la solución DP de Bellman Ford para la ruta más corta de fuente única. En Ford SSSP de Bellman, la idea principal es encontrar el siguiente vértice minimizando los bordes, podemos hacer lo mismo, minimizamos los valores abs de dos elementos de una array para encontrar el siguiente índice.
Para resolver cualquier problema de DP, primero adivinamos todas las soluciones posibles para los subproblemas y las memorizamos y luego elegimos las mejores soluciones para el subproblema. escribimos recurrencia para el problema
Recurrencia: DP(j) = min{DP(i) + abs(A[i] – A[j])} donde i está en [0, N-1] y j está en [i + 1, j + k + 1], y k es el número de saltos permitidos. esto también se puede comparar con la relajación en SSSP. Vamos a relajar cada próximo índice accesible.
//
nota del caso base[0] = 0;
para (i = 0 a N-1)
para (j = i+1 a i+k+1)
memo[j] = min(memo[j], memo[i] + abs(A[i] – A[ j]));
A continuación se muestra la implementación del enfoque Bottom-up above:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function for returning the min of two elements
int min(int a, int b) {
return (a > b) ? b : a;
}
int minCostJumpsDP(vector <int> & A, int k) {
// for calculating the number of elements
int size = A.size();
// Allocating Memo table and
// initializing with INT_MAX
vector <int> x(size, INT_MAX);
// Base case
x[0] = 0;
// For every element relax every reachable
// element ie relax next k elements
for (int i = 0; i < size; i++) {
// reaching next k element
for (int j = i + 1; j < i + k + 1; j++) {
// Relaxing the element
x[j] = min(x[j], x[i] + abs(A[i] - A[j]));
}
}
// return the last element in the array
return x[size - 1];
}
// Driver Code
int main()
{
vector <int> input { 83, 26, 37, 35, 33, 35, 56 };
cout << minCostJumpsDP(input, 3);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function for returning the
// min of two elements
static int min(int a, int b)
{
return (a > b) ? b : a;
}
static int minCostJumpsDP(int []A, int k)
{
// for calculating the number of elements
int size = A.length;
// Allocating Memo table and
// initializing with INT_MAX
int []x = new int[size];
Arrays.fill(x, Integer.MAX_VALUE);
// Base case
x[0] = 0;
// For every element relax every reachable
// element ie relax next k elements
for (int i = 0; i < size; i++)
{
// reaching next k element
for (int j = i + 1;
j < i + k + 1 &&
j < size; j++)
{
// Relaxing the element
x[j] = min(x[j], x[i] +
Math.abs(A[i] - A[j]));
}
}
// return the last element in the array
return x[size - 1];
}
// Driver Code
public static void main(String []args)
{
int []input = { 83, 26, 37, 35, 33, 35, 56 };
System.out.println(minCostJumpsDP(input, 3));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach import sys def minCostJumpsDP(A, k): # for calculating the number of elements size = len(A) # Allocating Memo table and # initializing with INT_MAX x = [sys.maxsize] * (size) # Base case x[0] = 0 # For every element relax every reachable # element ie relax next k elements for i in range(size): # reaching next k element j = i+1 while j < i + k + 1 and j < size: # Relaxing the element x[j] = min(x[j], x[i] + abs(A[i] - A[j])) j += 1 # return the last element in the array return x[size - 1] # Driver Code if __name__ == "__main__": input_ = [83, 26, 37, 35, 33, 35, 56] print(minCostJumpsDP(input_, 3)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Function for returning the
// min of two elements
static int min(int a, int b)
{
return (a > b) ? b : a;
}
static int minCostJumpsDP(int []A, int k)
{
// for calculating the number of elements
int size = A.Length;
// Allocating Memo table and
// initializing with INT_MAX
int []x = new int[size];
for (int i = 0; i < size; i++)
x[i] = int.MaxValue;
// Base case
x[0] = 0;
// For every element relax every reachable
// element ie relax next k elements
for (int i = 0; i < size; i++)
{
// reaching next k element
for (int j = i + 1;
j < i + k + 1 &&
j < size; j++)
{
// Relaxing the element
x[j] = min(x[j], x[i] +
Math.Abs(A[i] - A[j]));
}
}
// return the last element in the array
return x[size - 1];
}
// Driver Code
public static void Main(String []args)
{
int []input = { 83, 26, 37, 35, 33, 35, 56 };
Console.WriteLine(minCostJumpsDP(input, 3));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Function for returning the
// min of two elements
function min(a, b)
{
return (a > b) ? b : a;
}
function minCostJumpsDP(A, k)
{
// for calculating the number of elements
let size = A.length;
// Allocating Memo table and
// initializing with INT_MAX
let x = new Array(size);
for (let i = 0; i < size; i++)
x[i] = Number.MAX_VALUE;
// Base case
x[0] = 0;
// For every element relax every reachable
// element ie relax next k elements
for (let i = 0; i < size; i++)
{
// reaching next k element
for (let j = i + 1;
j < i + k + 1 &&
j < size; j++)
{
// Relaxing the element
x[j] = min(x[j], x[i] +
Math.abs(A[i] - A[j]));
}
}
// return the last element in the array
return x[size - 1];
}
let input = [ 83, 26, 37, 35, 33, 35, 56 ];
document.write(minCostJumpsDP(input, 3));
</script>
Producción:
69
Complejidad temporal: O(N * K)
Espacio auxiliar: O(N)