Geeks面试题:Min Cost Path

Min Cost Path

 

Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

For example, in the following figure, what is the minimum cost path to (2, 2)?
Geeks面试题:Min Cost Path

The path with minimum cost is highlighted in the following figure. The path is (0, 0) –> (0, 1) –> (1, 2) –> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).
Geeks面试题:Min Cost Path

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

下面是递归法和动态规划法的C++程序:

int minCostPath(vector<vector<int>> &cost, 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(minCostPath(cost, m-1, n-1),
min(minCostPath(cost, m-1, n), minCostPath(cost, m, n-1)));
} int minCostPathDP(vector<vector<int> > &cost)
{
int row = cost.size();
if (row < 1) return 0;
int col = cost[0].size(); vector<vector<int> > ta(2, vector<int>(col));
bool flag = false;
ta[!flag][0] = cost[0][0];
for (int i = 1; i < col; i++)
{
ta[!flag][i] = ta[!flag][i-1] + cost[0][i];
} for (int i = 1; i < row; i++)
{
ta[flag][0] = ta[!flag][0] + cost[i][0];
for (int j = 1; j < col; j++)
{
ta[flag][j] = min(min(ta[!flag][j],ta[flag][j-1]),
ta[!flag][j-1]) + cost[i][j];
}
flag = !flag;
}
return ta[!flag][col-1];
}
上一篇:超赞的.NET办公软件库


下一篇:IE和火狐的css兼容性问题