最小成本路径的C程序

在这里，我们将解决 C 语言中的最小成本路径问题。这意味着在 2D 矩阵上完成，其中每个单元格都有一个移动成本。我们必须找到一条从左上角到右下角且行程成本最小的路径。您只能从给定单元格向下和右下遍历单元格。

为了解决这个特定问题，动态编程比递归更好。

给定成本矩阵c ost[ ][ ] 和位置 (m,n)，我们必须编写一个函数，返回从 (0,0) 到达 (m,n) 的最小路径成本到达 (m, n) 的路径的总成本是该路径上所有成本的总和（包括源和目的地）。

假设− 所有成本是积极的。输入矩阵中不存在负成本循环

示例

查找到 (2,2) 的最小成本路径

费用在图像本身中给出。路径将为 (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2)。路径的值为 8 (1 +2+2+ 3)。

方法− 创建一个与给定矩阵大小相似的答案矩阵。

给定− arrA[ ][ ]。在每个单元格中，我们有 2 个选项（向右或向下），并且对于任何 i,j 单元格，我们可以选择这 2 个选项中的最小值。

solution[i][j]=A[0][j] if i=0, 1st row =A[i][0] if j=0, 1st column =A[i][j]+Min(solution[i=1],[j],solution[i][j-1]) if i>0 && j>0登录后复制

minimumCostPath[i][j] = minimum value to achieve (i, j) from (0, 0)登录后复制

minimumCostPath[0][0] = costMatrix[0][0] minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0], for all values of i > zero minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j], for all values of j >zero登录后复制

minimumCostPath[i][j] = costMatrix[i][j] +minimum(minimumCostPath[i - 1][j - 1],minimumCostPath[i - 1][j],minimumCostPath[i][j - 1])登录后复制

动态规划算法的时间复杂度为O(mn)。

示例

 实时演示

#include using namespace std; int min_(int a, int b, int c){ if (a < b) return (a < c) ? a : c; else return (b < c) ? b : c; } int min_cost(int cost[4][4], int m, int n){ int i, j; int tot_cost[4][4]; tot_cost[0][0] = cost[0][0]; for (i = 1; i