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).
Python
# Dynamic Programming Python implementation of Min Cost Path # problem R = 3 C = 3 def minCost(cost, m, n): # 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. tc = [[0 for x in range(C)] for x in range(R)] tc[0][0] = cost[0][0] # Initialize first column of total cost(tc) array for i in range(1, m + 1): tc[i][0] = tc[i-1][0] + cost[i][0] # Initialize first row of tc array for j in range(1, n + 1): tc[0][j] = tc[0][j-1] + cost[0][j] # Construct rest of the tc array for i in range(1, m + 1): for j in range(1, n + 1): tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j] return tc[m][n] # Driver program to test above functions cost = [[1, 2, 3], [4, 8, 2], [1, 5, 3]] print(minCost(cost, 2, 2)) # This code is contributed by Bhavya Jain
8
Tiempo Complejidad : 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