国内最有趣的网站,百元便宜建站,成都到西安需要核酸检测吗,装修设计师网站加qq1126137994 一起学习更多技术#xff01;#xff01;#xff01;
有一个矩阵map#xff0c;它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走#xff0c;最后到达右下角的位置#xff0c;路径上所有的数字累加起来就是路径和#xff0c;返回所有的…加qq1126137994 一起学习更多技术
有一个矩阵map它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走最后到达右下角的位置路径上所有的数字累加起来就是路径和返回所有的路径中最小的路径和。
给定一个矩阵map及它的行数n和列数m请返回最小路径和。保证行列数均小于等于100.
测试样例 [[1,2,3],[1,1,1]],2,3 返回4
分析 假设矩阵m的大小为M*N,行数为M列数为N生成大小和m一样的矩阵dp行数为M列数为Ndp[i][j]的值等于m矩阵从左上角也就是0,0 走到ij位置的最小路径和。 第一行与第一列通常都是可以通过一个循环求出来的 第一行的值只能是从左往右走路径最小值为前一个方格的路径最小值加上本方格所对应的权值即dp[0][j] dp[0][j-1]m[i][j] 第一列的值只能是从上往下走路径最小值为上一个方格的路径最小值加上本方格所对应的权值即dp[i][0] dp[i-1][0]m[i][j]
那么除了第一行和第一列的值其他部分的值为只能是从上面过来或者从左边过来 最终右下角的值就为我们所要求的值
实现代码如下
class MinimumPath {
public:int R_min(int m,int n){if(mn)return n;elsereturn m;}int getMin(vectorvectorint map, int n, int m) {// write code here//额外开辟一个dp矩阵并将dp矩阵所有值初始化为0vectorvectorint dp(n,vectorint(m,0));//矩阵的第一个空格的值就等于map矩阵的第一个值的本身dp[0][0] map[0][0];//先求第一行的值for(int j1;jm;j){dp[0][j] dp[0][j-1] map[0][j];}//再求第一列的值for(int i1;in;i){dp[i][0] dp[i-1][0] map[i][0];}//最后求其他行的值for(int i1;in;i){for(int j1;jm;j){dp[i][j]R_min(dp[i-1][j]map[i][j],dp[i][j-1]map[i][j]);}}return dp[n-1][m-1];}
};
以上程序求两个数的最小值并返回是可以不写的。可以直接用库函数min();但是我是因为不熟悉C的库函数所以自己写了一个影响不大
以上的分析思路依然是先解决子问题何为子问题就是我们把所要求的整体的问题化简到最简单的情况比如上面的题我们要求走到最右下角的路径的最小值那么我们就化简化简到整个矩阵为1个方格2个方格3个方格4个方格…… 时的最短路径的求解然后前面的子问题求出来了我们会发现通过前面子问题的整合可以求得整体问题也就是最终我们可以求得最右下角的值这也避免了很多的重复计算更加避免了递归所带来的复杂的运算顺序
