2014
03-07

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

1）最优子结构

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问题* /
#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;
}