LeetCode 64 Minimum Path Sum

Problem:文章来源地址:https://www.yii666.com/article/754004.html

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.文章地址https://www.yii666.com/article/754004.html

Summary:

想要从m*n的整型数矩阵左上角走到右下角,每次只可以向右或向下移动一步,求路径上的整型数最小情况下的数字之和。

Solution:

1. 暴力法:枚举从左上角到右下角的所有路径,分别计算出路径和并比较。但效率过低且明显不可行,故不考虑。

2. 动态规划:由于只可以向右或向下移动,若已知(i, j)位置上一格(i - 1, j)以及左一格(i, j - 1)的路径数字之和,即可确定该位置的路径数字和:

  dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])

  初始化:dp[0][0] = grid[0][0]网址:yii666.com

      dp[0][j] = dp[0][j - 1] + grid[0][j]网址:yii666.com<

      dp[i][0] = dp[i - 1][0] + grid[i][0]文章来源地址https://www.yii666.com/article/754004.html

 class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[].size();
vector<vector<int>> dp(row, vector<int>(col)); for (int i = ; i < row; i++) {
for (int j = ; j < col; j++) {
if (!i && !j) {
dp[i][j] = grid[i][j];
}
else if (!i && j) {
dp[i][j] = dp[i][j - ] + grid[i][j];
}
else if (i && !j) {
dp[i][j] = dp[i - ][j] + grid[i][j];
}
else {
dp[i][j] = min(dp[i - ][j], dp[i][j - ]) + grid[i][j];
}
}
} return dp[row - ][col - ];
}
};

3. 在法2的基础上优化空间

 class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[].size();
vector<int> dp(col); dp[] = grid[][];
for (int i = ; i < row; i++) {
for (int j = ; j < col; j++) {
if (!i && !j) {
dp[j] = grid[i][j];
}
else if (!i && j) {
dp[j] = dp[j - ] + grid[i][j];
}
else if (i && !j) {
dp[j] += grid[i][j];
}
else {
dp[j] = min(dp[j], dp[j - ]) + grid[i][j];
}
}
} return dp[col - ];
}
};

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png