首页 > 专题系列 > 算法分析 > 动态规划(6)-最小花费路径
2014
03-07

动态规划(6)-最小花费路径

第6讲,继续通过案例说明动态规划。

给定一个矩阵cost[][]和其中的一个位置(m,n),写一个函数,返回从到达(0,0)到(M,N)最小成本路径的花费。该矩阵的每个格子代表遍历该格子的花费。到达(M,N)的路径的总成本是该路径上(包括源和目标)所有的费用总和。你只能从开始位置 向右、下和右下走,也就是说,从一个给定的格子(I,J),只有(i+1,j)的(i,j +1)和(i +1, j +1)的可以通过。你可以假设所有的花费都是正整数。

例如,在下面的图中,到(2,2)的最小花费路径?

最小花费的路径,如下图高亮显示。的路径为(0,0) – >(0,1) – >(1,2) – >(2,2)。路径的成本是8(1 + 2 + 2 + 3)。

1)最优子结构
的路径到达(M,N)必须通过3格子中的一个:(M-1,N-1)或(m-1,n)或(M,N-1)。到达(M,N),所以最小的花费路径可以写成“3个格子最小的 加[M] [N]的花费”。

minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]

2)重叠子问题
以下是直接的递归实现的最小花费路径的问题,用的上面的递归函数

/* 直接的递归解决 MCP(Minimum Cost Path) 问题 */
#include<stdio.h>
#include<limits.h>
#define R 3
#define C 3

int min(int x, int y, int z);

/* 返回从 (0,0) 到 (m, n) 的最小花费*/
int minCost(int cost[R][C], int m, int n)
{
   if (n < 0 || m < 0)
      return INT_MAX;
   else if (m == 0 && n == 0)
      return cost[m][n];
   else
      return cost[m][n] + min( minCost(cost, m-1, n-1),
                               minCost(cost, m-1, n), 
                               minCost(cost, m, n-1) );
}

/* 返回三个数中最小的*/
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;
}

应当指出的是,上述函数反复计算相同的子问题。请参见下面的递归树。这时候直接的递归解决方案的复杂性是指数,这是极其缓慢的。

mC 代表 minCost()
                                    mC(2, 2)
                          /            |           \
                         /             |            \             
                 mC(1, 1)           mC(1, 2)             mC(2, 1)
              /     |     \       /     |     \           /     |     \ 
             /      |      \     /      |      \         /      |       \
       mC(0,0) mC(0,1) mC(1,0) mC(0,1) mC(0,2) mC(1,1) mC(1,0) mC(1,1) mC(2,0)

因此,MCP问题是具有动态规划必须的两个性质像其他典型的动态规划(DP)的问题,可通过打表已自下而上的方式避免相同的子问题重复计算。

/ *动态规划实现的MCP问题* /
#include<stdio.h>
#include<limits.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;
     int tc[R][C];  

     tc[0][0] = cost[0][0];

     /* 初始化第一列 cost(tc) array */
     for (i = 1; i <= m; i++)
        tc[i][0] = tc[i-1][0] + cost[i][0];

     /* 初始化第一行 */
     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];
}

/* 返回3个整数中最小的 */
int min(int x, int y, int z)
{
   if (x < y)
      return (x < z)? x : z;
   else
      return (y < z)? y : z;
}

/* 测试 */
int main()
{
   int cost[R][C] = { {1, 2, 3},
                      {4, 8, 2},
                      {1, 5, 3} };
   printf(" %d ", minCost(cost, 2, 2));
   return 0;
}

时间复杂度为O(MN)。

参考:http://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。