Dada una array de costo costo[][] y una posición (m, n) en costo[][], escriba una función que devuelva el costo del camino de costo mínimo para alcanzar (m, n) desde (0, 0). Cada celda de la array representa un costo para atravesar esa celda. El costo total de una ruta para llegar (m, n) es la suma de todos los costos en esa ruta (incluidos el origen y el destino). Solo puede recorrer las celdas hacia abajo, hacia la derecha y en diagonal desde una celda determinada, es decir, desde una celda determinada (i, j), celdas (i+1, j), (i, j+1) y (i+1, j+1) se puede atravesar. Puede suponer que todos los costos son números enteros positivos. Por ejemplo, en la siguiente figura, ¿cuál es la ruta de costo mínimo a (2, 2)?
La ruta con el costo mínimo se destaca en la siguiente figura. El camino es (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). El costo del camino es 8 (1 + 2 + 2 + 3).
C
/* Dynamic Programming implementation of MCP problem */
#include <limits.h>
#include <stdio.h>
#define R 3
#define C 3
int min(int x, int y, int z);
int minCost(int cost[R][C], int m, int n)
{
int i, j;
// Instead of following line, we can use int tc[m+1][n+1] or
// dynamically allocate memory to save space. The following line is
// used to keep te program simple and make it working on all compilers.
int tc[R][C];
tc[0][0] = cost[0][0];
/* Initialize first column of total cost(tc) array */
for (i = 1; i <= m; i++)
tc[i][0] = tc[i - 1][0] + cost[i][0];
/* Initialize first row of tc array */
for (j = 1; j <= n; j++)
tc[0][j] = tc[0][j - 1] + cost[0][j];
/* Construct rest of the tc array */
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
tc[i][j] = min(tc[i - 1][j - 1],
tc[i - 1][j],
tc[i][j - 1])
+ cost[i][j];
return tc[m][n];
}
/* 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;
}
/* Driver program to test above functions */
int main()
{
int cost[R][C] = { { 1, 2, 3 },
{ 4, 8, 2 },
{ 1, 5, 3 } };
printf(" %d ", minCost(cost, 2, 2));
return 0;
}
8
Complejidad del tiempo: O(m*n)
Espacio Auxiliar : O(m*n)
Consulte el artículo completo sobre programación dinámica | ¡ Establezca 6 (ruta de costo mínimo) para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA