为了解决这个特定问题，动态编程比递归更好。
给定成本矩阵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
算法答案中遵循的方法可以通过应用动态规划来有效地解决这个问题。创建大小为 m,n 的最小成本路径表并定义 -
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 > zerominimumcostpath[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])
这里，为了计算minimumcostpath[i][j]，我们倾向于使用minimumcostpath[i - 1][j - 1]、minimumcostpath[i - 1][j]和minimumcostpath[i][j - 1]作为结果，这些是我们达到minimumcostpath[i][j]的唯一允许的单元。最后，我们返回minimumcostpath[m][n]。
动态规划算法的时间复杂度为o(mn)。
示例 实时演示
#include <iostream>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 <= m; i++) tot_cost[i][0] = tot_cost[i - 1][0] + cost[i][0]; for (j = 1; j <= n; j++) tot_cost[0][j] = tot_cost[0][j - 1] + cost[0][j]; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) tot_cost[i][j] = min_(tot_cost[i - 1][j - 1], tot_cost[i - 1][j], tot_cost[i][j - 1]) + cost[i][j]; return tot_cost[m][n];}int main(){ int cost[4][4] = { { 9, 9, 4 }, { 8, 0, 9 }, {1, 2, 8} }; cout<<" the minimum cost is "<<min_cost(cost, 2, 2); return 0;}
输出the minimum cost is 17
以上就是最小成本路径的c程序的详细内容。