首页 > 试题广场 >

矩阵的最小路径和

[编程题]矩阵的最小路径和

热度指数：4465 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

数据范围: $1 \le n,m\le 500$ ，矩阵中任意值都满足 $0 \le a_{i,j} \le 100$

要求：时间复杂度 $O(nm)$

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，

所选择的最小累加和路径如下图所示：

输入描述:

第一行输入两个正整数 n 和 m 表示矩阵 a 的长宽
后续输入 n 行每行有 m 个数表示矩阵的每个元素

输出描述:

输出从左上角到右下角的最小路径和

示例1

输入

输出

示例2

输入

2 3
1 2 3
1 2 3

输出

算法知识视频讲解

C++

Spectre_

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int arr[n][m], dp[n][m];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) cin >> arr[i][j];
    // 时间复杂度O(NM)，空间复杂度O(NM)
    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(arr[i][j] + dp[i - 1][j], arr[i][j] + dp[i][j - 1]);
        }
    }
    cout << dp[n - 1][m - 1];
    return 0;
}

发表于 2022-11-01 11:24:06 回复(0)

C++

牛客212561046号

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin>>n>>m;
    vector<vector<int>> dp(n, vector<int>(m));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int x;
            cin>>x;
            if(i==0)  dp[i][j] = (j>0 ? dp[i][j-1] : 0) + x;
            else if(j==0) dp[i][j] = (i>0 ? dp[i-1][j] : 0) + x;
            else dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + x;
        }
    }
    cout<<dp[n-1][m-1];
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2023-12-29 16:18:24 回复(0)

呼延棋大宝

n , m = map(int,input().split())
mat = []

for i in range(n):
    mat.append(list(map(int,input().split())))

for i in range(n):
    for j in range(m):
        if i == 0 and j != 0:
            mat[i][j] = mat[i][j] + mat[i][j-1]
        elif i != 0 and j == 0:
            mat[i][j] = mat[i][j] + mat[i-1][j]
        elif i != 0 and j != 0:
            mat[i][j] = min(mat[i][j] + mat[i][j-1] , mat[i][j] + mat[i-1][j])

print(mat[n-1][m-1])

发表于 2023-04-20 23:18:20 回复(0)

燃烛续昼

状态转移方程

f(n, m) = min{f(n - 1, m), f(n, m - 1)} + value(n, m)

发表于 2023-03-04 20:44:39 回复(0)

小谷围做题家

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let [n,m]=(await readline()).split(" ").map(it=>parseInt(it));
    let matrix=[];
    while(line=await readline()){
        matrix.push(line.split(" ").map(it=>parseInt(it)));
    }
    for(let i=1;i<Math.max(n,m);i++){
        if(i<n) matrix[i][0]+=matrix[i-1][0];
        if(i<m) matrix[0][i]+=matrix[0][i-1];
    }
    for(let i=1;i<n;i++){
        for(let j=1;j<m;j++){
            matrix[i][j]+=Math.min(matrix[i-1][j],matrix[i][j-1]);
        }
    }
    console.log(matrix[n-1][m-1]);
}()

发表于 2022-11-30 18:52:16 回复(0)

Java

牛客208400313号

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[][] mat = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mat[i][j] = in.nextInt();
            }
        }

        // Base case
        for (int i = 1; i < n; i++) mat[i][0] += mat[i - 1][0];
        for (int j = 1; j < m; j++) mat[0][j] += mat[0][j - 1];

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                // 状态转移方程
                mat[i][j] += Math.min(mat[i - 1][j], mat[i][j - 1]);
            }
        }
        System.out.println(mat[n - 1][m - 1]);
    }
}

发表于 2022-10-03 16:48:32 回复(0)

C++

牛客288355985号

#include<iostream>
#include<algorithm>
using namespace std;

// dp[i][j]= a[i][j]+min(dp[i-1][j],dp[i][j-1])
// dp[-1][]=INF
// dp[][-1]=INF
// dp[0][0]=a[0][0]

const int INF=0x3f3f3f3f;

int a[509][509];
int cache[509][509];

int dp(int i, int j){
  if(i==0||j==0) return INF;
  if(i==1&&j==1) return a[0][0];
  if(cache[i][j]==0){
    cache[i][j]=a[i-1][j-1]+min(dp(i-1,j),dp(i,j-1));
  }
  return  cache[i][j];
}

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cin>>a[i][j];
    }
  }
  int res= dp(n,m);
  cout<<res<<endl;
}

发表于 2022-08-28 11:17:10 回复(0)

Python 3

Kiron_L

def solution(n, m, nums):
    if n == m == 1:
        return nums[0][0]
    if n == 1&nbs***bsp;m == 1:
        return sum(sum(nums[i] for i in range(n)))
    dp = [[0 for i in range(m)] for i in range(n)]
    dp[0][0] = nums[0][0]
    for j in range(1, m):
        dp[0][j] = sum(nums[0][0 : j + 1])
    for i in range(1, n):
        dp[i][0] = sum([nums[k][0] for k in range(0, i + 1)])
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + nums[i][j]
    return dp[-1][-1]


n, m = map(int, input().split())
nums = []
for i in range(n):
    nums.append(list(map(int, input().split())))
print(solution(n, m, nums))

发表于 2022-08-15 01:02:38 回复(0)

Java

charmingglobe

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        int[][] dp = new int[n][m];
        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 i = 1; i < m; i++) {
            dp[0][i] = dp[0][i-1] + arr[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + arr[i][j];
            }
        }
        System.out.println(dp[n-1][m-1]);
    }
}

发表于 2022-05-22 16:41:11 回复(0)

牛客79754087号

while True: try:
        n, m = map(int, input().split())
        numList = [] for i in range(n):
            numList.append(list(map(int, input().split()))) for i in range(1, m):
            numList[0][i] += numList[0][i - 1] for i in range(1, n):
            numList[i][0] += numList[i - 1][0] for i in range(1, n): for j in range(1, m):
                numList[i][j] = min(numList[i - 1][j] + numList[i][j], numList[i][j - 1] + numList[i][j]) print(numList[-1][-1]) except: break

发表于 2022-05-22 14:58:56 回复(0)

C/C++

牛客987690011号

只通过了5/10个测试用例，我实在想不出来为什么10行10列的情况下，每次提交得到的输出都不一样。

#include<stdio.h>
int main()
{
    int min(int,int);
    int n,m;scanf("%d %d",&n,&m);
    int grid[n][m];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&grid[i][j]);
        }
    }
    
    int dp[n][m];
    dp[0][0]=grid[0][0];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i==0&&j!=0)dp[i][j]=dp[i][j-1]+grid[i][j];
            else if(j==0&&i!=0)dp[i][j]=dp[i-1][j]+grid[i][j];
            else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }
    
    printf("%d",dp[n-1][m-1]);
    return 0;
}

int min(int a,int b)
{
    return (a<b?a:b);
}

发表于 2022-03-30 16:41:59 回复(0)

C++

Steph3

#include <iostream>
#include <vector>

using namespace std;

const int maxn = 510;
vector<vector<int>> mat(maxn, vector<int>(maxn, 0));

int n, m;

int main()
{
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> mat[i][j];
            }
        }
        
        vector<vector<int>> dp(maxn, vector<int>(maxn));
        for (int i = 1; i <= n; i++) dp[i][1] = dp[i-1][1] + mat[i][1];
        for (int j = 1; j <= m; j++) dp[1][j] = dp[1][j-1] + mat[1][j];
        
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + mat[i][j];
            }
        }
        cout << dp[n][m] << endl;
    }
}

发表于 2022-03-05 10:55:56 回复(0)

C++