欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划-矩阵最小路径和

程序员文章站 2022-07-12 12:15:33
...

题目描述

有一个矩阵map,它每个格子有一个权值。
从左上角的格子开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和。
返回所有的路径中最小的路径和。
给定一个矩阵map及它的行数n和列数m,请返回最小路径和。

求解过程

给定一个N*M的矩阵,假定N等于4,M等于4
1 2 3 4
4 8 3 2
6 1 4 5
7 3 7 8

现在生成一个大小为N*M的矩阵dp, dp[i][j]的含义为从(0,0)点到(i,j)点的最小路径
显然 第一行的路径值就为从0,0点到i,j 每一点值的和

1 3 6 10
1
5
11
18              

置dp[0][0] = 矩阵值[0][0];
对于第一行来说: dp[i][0] = dp[i-1][0] + 矩阵值[i][0];
对于第一列来说: dp[0][i] = dp[0][i-1] + 矩阵值[0][i];
对于除第一行第一列之后其他的位置有: 
    dp[i][j] = min(dp[i-1][j] ,dp[i][j-1])+ 矩阵值[i][j];
至此,状态转移方程求解完毕

代码实现

class MinimumPath 
{
public:
    int getMin(vector<vector<int> > juzhen, int n, int m)
     {
        vector<vector<int> >dp(n,vector<int>(m,0));
        dp[0][0] = juzhen[0][0];
        for (int i=1; i<n; ++i)
            dp[i][0] = dp[i-1][0] + juzhen[i][0];
        for (int i=1; i<m; ++i)
            dp[0][i] = dp[0][i-1] + juzhen[0][i];
        for(int i=1; i<n; ++i)
        {
            for (int j=1; j<m; ++j)
            {
                dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + juzhen[i][j];
            }
        }
        return dp[n-1][m-1];
    }
};