鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

lintcode 110最小路径和

来源:互联网 作者:佚名 时间:2018-02-27 09:50
最小路径和 描述 笔记 数据 评测 给定一个只含非负整数的m*n网格,找到一条从左上角到右下角的可以使数字和最小的路径。 注意事项 你在同一时间只能向下或者向右移动一步 您在真实的面试中是否遇到过这个题? Yes 哪家公司问你的这个题? LinkedIn Amazon Ai

最小路径和

 

给定一个只含非负整数的m*n网格,找到一条从左上角到右下角的可以使数字和最小的路径。

 

注意事项

你在同一时间只能向下或者向右移动一步

您在真实的面试中是否遇到过这个题? Yes 哪家公司问你的这个题? LinkedIn Amazon Airbnb Cryptic Studios Dropbox Epic Systems TinyCo Hedvig Uber Yelp Apple Yahoo Bloomberg Zenefits Twitter Microsoft Google Snapchat Facebook 感谢您的反馈 样例   标签 动态规划 相关题目 1 (dynamic-programming) 容易 数字三角形 26 % 2 (dynamic-programming),(divide-and-conquer),(recursion) 中等 二叉树中的最大路径和 25 %     每次只能向下或者向右走,所以本题可以按行或者按列进行更新  
class Solution {
public:
    /*
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    int minPathSum(vector<vector<int>> &grid) {
        // write your code here
        int x=grid.size();
        int y=grid[x-1].size();
        for(int i =0;i<x;i++){
            for(int j=0;j<y;j++){
                if(i==0&&j==0)
                    continue;
                else if(i==0)
                    grid[i][j]+=grid[i][j-1];
                else if(j==0)
                    grid[i][j]+=grid[i-1][j];
                else
                    grid[i][j]=grid[i][j]+min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[x-1][y-1];
    }
};

  

   
网友评论
<