题解 | #矩阵的最小路径和#

矩阵的最小路径和

http://www.nowcoder.com/practice/38ae72379d42471db1c537914b06d48e

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin >> n >>m;
    vector<vector<int> >arr(n,vector<int>(m));
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            cin >> arr[i][j];
        }
    }
    vector<vector<int> >dp(n,vector<int>(m,0));
    dp[0][0] = arr[0][0];
    for(int i = 1;i < n;i++)dp[i][0] =dp[i-1][0] + arr[i][0];
    for(int j = 1;j < m;j++)dp[0][j] =dp[0][j-1] + arr[0][j];
    for (int i = 1;i < n;i++)
    {
        for(int j = 1;j < m;j++)
        {
            dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + arr[i][j];
        }
    }
    cout<<dp[n-1][m-1];
    return 0;
    
}
全部评论

相关推荐

点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务