rom right ott path sum 处理 tom ber its
题目:
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.
题解:
Solution 1 ()
- class Solution {
- public:
- intminPathSum(vectorint>>& grid) {
- intm = (int) grid.size(), n = (int) grid[0].size();
- vector<long> dp(n,INT_MAX);
- dp[0] = grid[0][0];
- for(inti=0; ii) {
- for(intj=0; jj) {
- if(j >0)
- dp[j] = min(dp[j] + grid[i][j], dp[j-1] + grid[i][j]);
- else
- if(i>0) dp[j] = dp[j] + grid[i][j];
- }
- }
- returndp[n-1];
- }
- };
边界的第二种处理方法:因为 Solution 1 中 dp 初始化为最大值,故需要考虑溢出情况,所以用 long 整型。这个就初始化为 int 整型。
Solution 2 ()
- class Solution {
- public:
- intminPathSum(vectorint>>& nums) {
- intm = (int) nums.size();
- intn = (int) nums[0].size();
- vector<int> v (n,0);
- for(inti=0; ii) {
- for(intj=0; jj) {
- if(i>0)
- v[j] = nums[i][j] + ((j>0) ? min(v[j], v[j-1]) : v[j]);
- else
- v[j] = nums[i][j] + ((j>0) ? v[j-1] :0);
- }
- }
- returnv[n-1];
- }
- };
解法没变,就是边界的处理上不一样,这个是先初始化边界了。
Solution 3 ()
- class Solution {
- public:
- intminPathSum(vectorint>>& grid) {
- intdp[grid.size()][grid[0].size()];
- dp[0][0] = grid[0][0];
- // init first row
- for(inti =1; i < grid[0].size(); i ++){
- dp[0][i] = dp[0][i-1] + grid[0][i];
- }
- // init first col
- for(inti =1; i < grid.size(); i ++){
- dp[i][0] = dp[i-1][0] + grid[i][0];
- }
- for(inti =1; i < grid.size(); i ++){
- for(intj =1; j < grid[0].size(); j++){
- dp[i][j] = dp[i -1][j] < dp[i][j-1]? dp[i -1][j] + grid[i][j] : dp[i][j-1] + grid[i][j];
- }
- }
- returndp[grid.size() -1][grid[0].size() -1];
- }
- };
【LeetCode】064. Minimum Path Sum
来源: http://www.bubuko.com/infodetail-2058408.html