Dado un número entero N y tres N x N arrays X[][] , Y[][] y Z[][] , la tarea es calcular el costo mínimo requerido para llegar a la parte inferior derecha desde la parte superior izquierda de la array utilizando los siguientes movimientos:
- Muévase a una celda en la dirección correcta desde (i, j) que costará X[i][j] .
- Muévase a una celda en la dirección hacia abajo desde (i, j) que costará Y[i][j] .
- Muévase a una celda en la dirección diagonal desde (i, j) que costará Z[i][j] ,
Ejemplo:
Entrada: N = 3, X[][] = {{1, 2, 1}, {3, 4, 5}, {1, 1, 1}}, Y[][] = {{2, 3, 4}, {1, 3, 1}, {2, 1, 1}}, Z[][] = {{1, 8, 9}, {1, 4, 5}, {6, 5, 4} }.
Salida: 4
Explicación: El camino que conducirá al costo mínimo es el siguiente:
- En el primer movimiento, muévase hacia abajo de (0, 0) a (1, 0), lo que agregará un costo de 2.
- En el segundo movimiento, muévase en diagonal de (1, 0) a (2, 1), lo que agregará un costo de 1.
- En el tercer y último movimiento, muévase a la derecha de (2, 1) a (2, 2), lo que agregará un costo de 1.
Por lo tanto, el costo total requerido es 4, que es el mínimo posible.
Entrada: N = 2, X[][] = {{1, 1}, {1, 1}}, Y[][] = {{1, 1}, {1, 1}}, Z[][ ] = {{1, 1}, {1, 1}}
Salida: 1
Enfoque: El problema dado sigue una estructura similar al problema estándar de ruta de costo mínimo . Se puede resolver mediante programación dinámica . El camino para llegar a (i, j) debe ser a través de una de las 3 celdas: (i-1, j-1) o (i-1, j) o (i, j-1) . Entonces, el costo mínimo para alcanzar (i, j) se puede escribir como la siguiente relación:
minCost(i, j) = min ( minCost(i, j – 1) + X[i][j – 1],
minCost(i – 1, j) + Y[i – 1][j],
minCost(i – 1, j – 1) + Z[i – 1][j – 1])
Por lo tanto, cree una array 2D dp[][] , donde dp[i – 1][j – 1] almacene el costo mínimo para llegar a la celda (i, j) desde (0, 0) y complete el dp[][ ] array de forma ascendente . El valor almacenado en dp[N – 1][N – 1] es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
#include <limits.h>
#define R 3
#define C 3
using namespace std;
// A utility function that returns
// minimum of 3 integers
int min(int x, int y, int z)
{
if (x < y)
return (x < z) ? x : z;
else
return (y < z) ? y : z;
}
// Function to find the min cost path
int minCost(int X[R][C], int Y[R][C],
int Z[R][C], int n)
{
int i, j;
// 2D array to store DP states
int dp[R][C];
dp[0][0] = 0;
// Initialize first row of dp array
for (j = 1; j < n; j++)
dp[0][j] = dp[0][j - 1] + X[0][j - 1];
// Initialize first column of dp array
for (i = 1; i < n; i++)
dp[i][0] = dp[i - 1][0] + Y[i - 1][0];
// Construct rest of the dp array
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
// Calculating the minimum over
// the downward, right or the
// diagonal movement
dp[i][j]
= min(
dp[i - 1][j - 1] + Z[i - 1][j - 1],
dp[i - 1][j] + Y[i - 1][j],
dp[i][j - 1] + X[i][j - 1]);
// Return answer
return dp[n - 1][n - 1];
}
// Driver code
int main()
{
int N = 3;
int X[R][C] = { { 1, 2, 1 },
{ 3, 4, 5 },
{ 1, 1, 1 } };
int Y[R][C] = { { 2, 3, 4 },
{ 1, 3, 1 },
{ 2, 1, 1 } };
int Z[R][C] = { { 1, 8, 9 },
{ 1, 4, 5 },
{ 6, 5, 4 } };
cout << minCost(X, Y, Z, 3);
return 0;
}
Java
// Java program of the above approach
//include <limits.h>
import java.util.*;
class GFG{
static final int R = 3;
static final int C = 3;
// A utility function that returns
// minimum of 3 integers
static int min(int x, int y, int z)
{
if (x < y)
return (x < z) ? x : z;
else
return (y < z) ? y : z;
}
// Function to find the min cost path
static int minCost(int X[][], int Y[][],
int Z[][], int n)
{
int i, j;
// 2D array to store DP states
int dp[][] = new int[R][C];
dp[0][0] = 0;
// Initialize first row of dp array
for (j = 1; j < n; j++)
dp[0][j] = dp[0][j - 1] + X[0][j - 1];
// Initialize first column of dp array
for (i = 1; i < n; i++)
dp[i][0] = dp[i - 1][0] + Y[i - 1][0];
// Conrest of the dp array
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
// Calculating the minimum over
// the downward, right or the
// diagonal movement
dp[i][j]
= Math.min(Math.min(
dp[i - 1][j - 1] + Z[i - 1][j - 1],
dp[i - 1][j] + Y[i - 1][j]),
dp[i][j - 1] + X[i][j - 1]);
// Return answer
return dp[n - 1][n - 1];
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int X[][] = { { 1, 2, 1 },
{ 3, 4, 5 },
{ 1, 1, 1 } };
int Y[][] = { { 2, 3, 4 },
{ 1, 3, 1 },
{ 2, 1, 1 } };
int Z[][] = { { 1, 8, 9 },
{ 1, 4, 5 },
{ 6, 5, 4 } };
System.out.print(minCost(X, Y, Z, 3));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code for the above approach R = 3 C = 3 # A utility function that returns # minimum of 3 integers def min(x, y, z): if (x < y): return x if (x < z) else z; else: return y if (y < z) else z; # Function to find the min cost path def minCost(X, Y, Z, n): i = None j = None # 2D array to store DP states dp = [0] * R; for i in range(len(dp)): dp[i] = [0] * C dp[0][0] = 0; # Initialize first row of dp array for j in range(1, n): dp[0][j] = dp[0][j - 1] + X[0][j - 1]; # Initialize first column of dp array for i in range(1, n): dp[i][0] = dp[i - 1][0] + Y[i - 1][0]; # Construct rest of the dp array for i in range(1, n): for j in range(1, n): # Calculating the minimum over # the downward, right or the # diagonal movement dp[i][j] = min( dp[i - 1][j - 1] + Z[i - 1][j - 1], dp[i - 1][j] + Y[i - 1][j], dp[i][j - 1] + X[i][j - 1]); # Return answer return dp[n - 1][n - 1]; # Driver code N = 3; X = [[1, 2, 1], [3, 4, 5], [1, 1, 1]]; Y = [[2, 3, 4], [1, 3, 1], [2, 1, 1]]; Z = [[1, 8, 9], [1, 4, 5], [6, 5, 4]]; print(minCost(X, Y, Z, 3)); # This code is contributed by gfgking
C#
// C# program of the above approach
using System;
class GFG {
static int R = 3;
static int C = 3;
// A utility function that returns
// minimum of 3 integers
static int min(int x, int y, int z)
{
if (x < y)
return (x < z) ? x : z;
else
return (y < z) ? y : z;
}
// Function to find the min cost path
static int minCost(int [,]X, int [,]Y,
int [,]Z, int n)
{
int i, j;
// 2D array to store DP states
int [,]dp = new int[R, C];
dp[0, 0] = 0;
// Initialize first row of dp array
for (j = 1; j < n; j++)
dp[0, j] = dp[0, j - 1] + X[0, j - 1];
// Initialize first column of dp array
for (i = 1; i < n; i++)
dp[i, 0] = dp[i - 1, 0] + Y[i - 1, 0];
// Conrest of the dp array
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
// Calculating the minimum over
// the downward, right or the
// diagonal movement
dp[i, j]
= Math.Min(Math.Min(
dp[i - 1, j - 1] + Z[i - 1, j - 1],
dp[i - 1, j] + Y[i - 1, j]),
dp[i, j - 1] + X[i, j - 1]);
// Return answer
return dp[n - 1, n - 1];
}
// Driver code
public static void Main()
{
int N = 3;
int [,]X = { { 1, 2, 1 },
{ 3, 4, 5 },
{ 1, 1, 1 } };
int [,]Y = { { 2, 3, 4 },
{ 1, 3, 1 },
{ 2, 1, 1 } };
int [,]Z = { { 1, 8, 9 },
{ 1, 4, 5 },
{ 6, 5, 4 } };
Console.Write(minCost(X, Y, Z, 3));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
let R = 3
let C = 3
// A utility function that returns
// minimum of 3 integers
function min(x, y, z) {
if (x < y)
return (x < z) ? x : z;
else
return (y < z) ? y : z;
}
// Function to find the min cost path
function minCost(X, Y,
Z, n) {
let i, j;
// 2D array to store DP states
let dp = new Array(R);
[C];
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(C)
}
dp[0][0] = 0;
// Initialize first row of dp array
for (j = 1; j < n; j++)
dp[0][j] = dp[0][j - 1] + X[0][j - 1];
// Initialize first column of dp array
for (i = 1; i < n; i++)
dp[i][0] = dp[i - 1][0] + Y[i - 1][0];
// Construct rest of the dp array
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
// Calculating the minimum over
// the downward, right or the
// diagonal movement
dp[i][j]
= Math.min(
dp[i - 1][j - 1] + Z[i - 1][j - 1],
dp[i - 1][j] + Y[i - 1][j],
dp[i][j - 1] + X[i][j - 1]);
// Return answer
return dp[n - 1][n - 1];
}
// Driver code
let N = 3;
let X = [[1, 2, 1],
[3, 4, 5],
[1, 1, 1]
];
let Y = [[2, 3, 4],
[1, 3, 1],
[2, 1, 1]];
let Z = [[1, 8, 9],
[1, 4, 5],
[6, 5, 4]];
document.write(minCost(X, Y, Z, 3));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )