首页 > 试题广场 >

矩阵的最小路径和

[编程题]矩阵的最小路径和
  • 热度指数:10347 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个 n * m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。

输入描述:
第一行输入两个整数 n 和 m,表示矩阵的大小。

接下来 n 行每行 m 个整数表示矩阵。


输出描述:
输出一个整数表示答案。
示例1

输入

4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

输出

12

备注:

动态规划模版题,上边界只能从左边转移过来,左边界只能从上边转移过来,其他位置从上边和左边中选择代价小的方式转移过来。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        int[][] grid = new int[n][m];
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            for(int j = 0; j < m; j++)
                grid[i][j] = Integer.parseInt(params[j]);
        }
        for(int i = 1; i < m; i++) grid[0][i] += grid[0][i - 1];
        for(int i = 1; i < n; i++) grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++)
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
        System.out.println(grid[n - 1][m - 1]);
    }
}

发表于 2021-11-21 19:53:30 回复(0)
菜鸡第一次独立思考解决掉的问题。。。
目前我对动态规划的理解,很多时候需要借助一个额外的存储空间(记忆空间)来解决,和刚开始学编程用一个flag变量来记录状态一样。

问题既然是求到最后一个位置的最小值,那么最后一个位置的值是怎么来的呢?按照动态规划的思想,必然是来自前一个记录位置的较小值加上最后一个位置的值,肯定是最小的,以此回推。由于移动的方向只能是向右和向下,最后一个位置最小,必然是从它的左边或者正上方那个较小的值而来。
按照这种思路,第一个位置时,就是它本身。第一行都是是向右所得,第一列都是向下移动所得,从第2行和第2列开始,这里先求出来,直接从第2行和第2列开始,直到最后一个位置。这里求出第1行和第1列的值我也是为了最后循环方便

这里是自顶向下,我也知道最好是从自底向上,但是先这样,慢慢养成思维习惯!!加油!!!

代码
import java.util.Scanner;
public class Main{
    public static int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];      //起点位置
        //求第1列的值
        for(int i = 1;i<grid.length;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        //求第1行的值
        for(int i = 1;i<grid[0].length;i++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        //循环结束,最后的结果即为最小值
        for(int i = 1;i<grid.length;i++){
            for(int j = 1;j<grid[0].length;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }

        return dp[grid.length-1][grid[0].length-1];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j = 0;j<m;j++){
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(minPathSum(arr));
    }
}


发表于 2020-04-14 17:01:18 回复(0)
动态规划
#include<stdio.h>
(737)#include<stdlib.h>
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	int** a = (int**)malloc(sizeof(int*) * n);
	int** dp = (int**)malloc(sizeof(int*) * n);
	//
	for (int i = 0; i <= n - 1; i++)
	{
		a[i] = (int*)malloc(sizeof(int) * m);
		dp[i] = (int*)malloc(sizeof(int) * m);
	}
	//
	for (int i = 0; i <= n-1; i++)
	{
		for (int j = 0; j <= m-1; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	////
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			if (i == 0 && j == 0) dp[i][j] = a[i][j];
			else if (i == 0)  dp[i][j] = dp[i][j - 1] + a[i][j];
			else if (j == 0)  dp[i][j] = dp[i - 1][j] + a[i][j];
			else dp[i][j]= min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
		}
	}
	//
	printf("%d", dp[n - 1][m - 1]);
	
	return 0;
}

编辑于 2020-04-14 10:16:47 回复(1)
动态规划问题
方法一:
1.生成大小和输入矩阵vec一样大小的矩阵dp,dp[i][j]表示从左上角(0,0)位置走到(i,j)位置的最小路径
2.第一行所有位置只能向右走,所以(0,0)位置到(0,j)位置的路径和就是vec[0][0...j]的值累加,同理,对于第一列的所有位置来说,只能向下走,为vec[0...i][0]的累加
3.除第一行和第一列其他位置都有左位置和上位置,选择值最小的位置加上当前值vec[i][j]就是就是当前路径最小值
时间复杂度O(row*col) 空间复杂度O(row*col)
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int minPathSum1(const vector<vector<int>>& vec)
{
    int row=vec.size();
    int col=vec[0].size();
    if(vec.empty()||row==0||col==0)return 0;
    vector<vector<int>> dp(row,vector<int>(col,0));
    dp[0][0]=vec[0][0];
    for(int i=1;i<row;++i)dp[i][0]=dp[i-1][0]+vec[i][0];
    for(int j=1;j<col;++j)dp[0][j]=dp[0][j-1]+vec[0][j];
    for(int i=1;i<row;++i)
    {
        for(int j=1;j<col;++j)
        {
            dp[i][j]=min(dp[i-1][j],dp[i][j-1])+vec[i][j];
        }
    }
    return dp[row-1][col-1];
}



int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>>arr;
    int val;
    for(int i=0;i<n;++i)
    {
        vector<int> var;
        for(int j=0;j<m;++j)
        {
            cin>>val;
            var.push_back(val);
        }
        arr.push_back(var);
    }
    int res=minPathSum1(arr);
    cout<<res<<endl;
    return 0;
}
方法二:
1.判断行和列哪个比较小,分别记为more和less
2.生成一个长度为less数组arr,用于存储less方向上最小路径和的值
3.沿着more的方向滚动,每次比较左边值和上边值大小并相加
int minPathSum2(const vector<vector<int>>& vec)
{
    int row=vec.size();
    int col=vec[0].size();
    if(vec.empty()||row==0||col==0)return 0;
    int more,less;
    bool rowmore=false;
    if(row>col)
    {
        rowmore=true;
        more=row,less=col;
    }else{
        more=col,less=row;
    }
    vector<int> arr(less,0);//辅助数组为行数与列数中最小值
    arr[0]=vec[0][0];
    for(int i=1;i<less;++i)
    {
        arr[i]=arr[i-1]+(rowmore?vec[0][i]:vec[i][0]);
    }
    for(int i=1;i<more;++i)
    {
        arr[0]=arr[0]+(rowmore?vec[i][0]:vec[0][i]);
        for(int j=1;j<less;++j){
            arr[j]=min(arr[j-1],arr[j])+(rowmore?vec[i][j]:vec[j][i]);
            
        }
    }
    return arr[less-1];
}


编辑于 2019-08-11 17:50:11 回复(0)
#include <bits/stdc++.h>
using namespace std;

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

发表于 2020-05-25 00:24:59 回复(1)
#include <bits/stdc++.h>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> A(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];
        }
    }
    
    vector<int> dp(A[0]);
    for (int j = 1; j < m; j++) {
        dp[j] += dp[j - 1];
    }
    
    for (int i = 1; i < n; i++) {
        dp[0] = dp[0] + A[i][0];
        for (int j = 1;j < m; j++) {
            dp[j] = min(dp[j - 1], dp[j]) + A[i][j];
        }
    }
    
    cout << dp.back() << endl;
    return 0;
}

发表于 2021-09-12 14:04:34 回复(0)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        int result = minPathSum(matrix);
        System.out.println(result);
    }
    
    public static int minPathSum(int[][] m) {
        int row = m.length, col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                if (i == 0) {
                    dp[i][j] = m[i][j] + dp[i][j - 1];
                } else if (j == 0) {
                    dp[i][j] = m[i][j] + dp[i - 1][j];
                } else {
                    dp[i][j] = m[i][j] + Math.min(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[row - 1][col - 1];
    }
}

发表于 2021-04-09 17:19:58 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int f(vector<vector<int>> v) {
    int m = v.size();
    int n = v[0].size();
    if (m == 0 || n == 0)
        return 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = v[0][0];
    for (int i = 1; i < n; i++) {
        dp[0][i] = dp[0][i - 1] + v[0][i];
    }
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + v[i][0];
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + v[i][j];
        }
    }
    return dp[m - 1][n - 1];
}
int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>>v(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> v[i][j];
        }
    }
    cout << f(v) << endl;
    return 0;
}
发表于 2020-07-01 10:34:17 回复(0)
第一步:用input()或者sys.stdin.readline()读数(ps:容易遗忘)
第二步:将读的数据转化矩阵并修改格式为整数
row,clo = map(int, sys.stdin.readline().strip().split())
mat = [[int(v) for v in sys.stdin.readline().strip().split()] for i in range(row)]
第三步:第一种情况:列和行或者矩阵为空的情况,输出为0
第四步:第二种情况:输入是一行数据,结果就有一个,就是sum(mat[0])
第五步:第三种情况:输入是一列数据,结果就有一个,所有元素相加,小心python取法
for j in range(1,row):
     mat[j][0]= mat[j][0]+mat[j-1][0]
结果是mat[row-1][0]
第六步:第四种情况:输入二维数组,新建矩阵newMat,第一行的元素只能向右走,那么新矩阵的第一行元素值就是newMat[0[[j] = mat[0][j]+mat[0][j-1],第一列元素只能向下走,那么新矩阵的第一列元素就是newMat[i][0]= mat[i][0]+mat[i-1][0],再从下标为1,1开始,newMat[1][1]的值是newMat[1][1]=mat[1][1]+min(newMat[0][1]newMat[1][0]),依次类推:newMat[i][j] = mat[i][j]+min(newMat[i-1][j]newMat[i][j-1])

发表于 2020-06-07 18:08:29 回复(0)
动态规划
import java.util.Scanner;

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

    public static int minSum(int[][] value, int n, int m){
        // 表示第i行j列的最小路径和
        int[][] min = new int[n][m];
        min[0][0] = value[0][0];
        for(int i=1;i<n;i++){
            min[i][0] = min[i-1][0] + value[i][0];
        }
        for(int i=1;i<m;i++){
            min[0][i] = min[0][i-1] + value[0][i];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                min[i][j] = Math.min(min[i-1][j], min[i][j-1]) + value[i][j];
            }
        }
        return min[n-1][m-1];
    }

}


发表于 2020-05-07 17:47:04 回复(0)
        基于动态规划思想,使用了dp[i][j]存储:到第i行,j列最短路径。遍历完毕后,最后直接输出到右下角点的最短路径就可以。
import java.util.*;
public class Main1{
    
    static int findMin(int[][] path,int row,int col) {
        if(row<1||col<1)
            return -1;
        else if(row==1&&col==1)
            return path[0][0];
        else if(row==1) {
            int min=0;
            for(int i=0;i<col;i++) {
                min+=path[0][i];
            }
            return min;
        }
        else if(col==1) {
            int min=0;
            for(int i=0;i<row;i++) {
                min+=path[i][0];
            }
            return min;
        }
        int[][] dp=new int[row][col];
        dp[0][0]=path[0][0];
        for(int i=1;i<row;i++) {
            dp[i][0]=dp[i-1][0]+path[i][0];
        }
        for(int i=1;i<col;i++) {
            dp[0][i]=dp[0][i-1]+path[0][i];
        }
        
        for(int i=1;i<row;i++) {
            for(int j=1;j<col;j++) {
                dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+path[i][j];
            }
        }
        return dp[row-1][col-1];
    }
    
    public static void main(String[] args){
        int row;int col;
        Scanner in=new Scanner(System.in);

        while(in.hasNext()){
            row=in.nextInt();
            col=in.nextInt();
            int[][] path=new int[row][col];
            for(int i=0;i<row;i++) {
                for(int j=0;j<col;j++) {
                    path[i][j]=in.nextInt();
                }
            }
            System.out.println(findMin(path,row,col));
        }
    }
}


发表于 2020-04-23 17:43:59 回复(0)
本题动态规划求解的核心在于,问题的规模增长的方式为,1*m ->n*m。把握这个核心,参看代码就很容易看懂了,本人的代码是抄的....
发表于 2020-02-25 19:00:32 回复(0)
#include <vector>
#include <iostream>
#include <cstdio>

using namespace std;


/**
 * 读数据
 * @param n 行数
 * @param m 列数
 * @param matrix 数组
 * @return 空
 */
void read_data(int &n, int &m, vector<vector<int>> &matrix) {
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        vector<int> vec_temp;
        for (int j = 0; j < m ; j++) {
            int element;
            scanf("%d", &element);
            
            vec_temp.push_back(element);
        }
        
        matrix.push_back(vec_temp);
    }
    
    return;
}


/**
 * 求最小路径和
 * @param n 行数
 * @param m 列数
 * @param matrix n*m数组
 * @return 最小路径和
 */
int min_path(int n, int m, vector<vector<int>> &matrix) {
    // 记录行走距离的矩阵
    vector<vector<int>> move_distance_matrix;
    move_distance_matrix.resize(n);
    for (int i = 0; i < n; ++i) {
        move_distance_matrix[i].resize(m);
    }
    
    for (int j = 0; j < n; ++j) {
        for (int k = 0; k < m; k++) {
            if (j == 0 && k == 0) {
                move_distance_matrix[j][k] = matrix[j][k];
            } else if (j == 0) {
                move_distance_matrix[j][k] = move_distance_matrix[j][k - 1] + matrix[j][k];
            } else if (k == 0) {
                move_distance_matrix[j][k] = move_distance_matrix[j - 1][k] + matrix[j][k];
            } else {
                int right = move_distance_matrix[j][k - 1] + matrix[j][k];
                int down = move_distance_matrix[j - 1][k] + matrix[j][k];
                
                move_distance_matrix[j][k] = right > down ? down : right;
            }
        }
    }
    
    return move_distance_matrix[n - 1][m - 1];
}


int main() {
    int n;
    int m;
    vector<vector<int>> matrix;
    
    read_data(n, m, matrix);
    
    cout << min_path(n, m, matrix);
}
编辑于 2020-01-01 01:45:00 回复(0)
//参考别人的
#include<stdio.h>
int main()
{
	int i, j, n, m;
	scanf("%d %d", &n, &m);
	int a[10][10];
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &a[i][j]);
	 for (i = 0; i < n; i++)
	{
		for (j = 0; j < m; j++)
		{
			if (i == 0 && j == 0)
				a[i][j] = 1;
			else {
				if (i == 0 && j != 0)
					a[i][j] += a[i][j - 1];
				else
				{
					if (j == 0 && i != 0)
						a[i][j] += a[i - 1][j];
					else
					{
						if (a[i - 1][j] < a[i][j - 1])
							a[i][j] += a[i - 1][j];
						else a[i][j] += a[i][j - 1];
					}
				}
			}
		}
	}
	printf("%d", a[n - 1][m - 1]);
	return 0;
	
}

发表于 2019-10-20 22:53:15 回复(0)
a[i][j]的最短路径和,为左边坐标与上边标准两个中的最小值。考虑数组边界
分4中情况。
情况1、i=0并且j=0,a[i][j]的结果为a[0][0]
情况2、i=0,j!=0 ,a[i][j]的结果为a[0][j-j]
情况3、j=0,i!=0,a[i][j]的结果为a[i-1][j]
情况4,i!=0,j!=0,a[i][j]的结果为a[i-1][j-1]

所以,考虑两个for循环遍历二维数组,上边的值和左边的值,肯定先计算出来。只要循环完就计算完了。
发表于 2019-10-18 14:21:43 回复(0)

根据LeetCode 64的思路写的,从右下角开始反着求

#include<iostream>
#include<vector>
using namespace std;
int min_path_length(vector<vector<int> >matrix)
{
    int row=matrix.size(),col=matrix[0].size();
    const int j=row;
    const int k=col;
    int dp[j][k];
    for(int i=row-1;i>=0;i--)
    {
        for(int j=col-1;j>=0;j--)
        {
            if(i==row-1 && j!=col-1)
            {
                dp[i][j]=matrix[i][j]+dp[i][j+1];
            }
            else if(i!=row-1 && j==col-1)
            {
                dp[i][j]=matrix[i][j]+dp[i+1][j];
            }
            else if(i!=row-1 && j!=col-1)
            {
                dp[i][j]=matrix[i][j]+min(dp[i+1][j],dp[i][j+1]);
            }
            else
            {
                dp[i][j]=matrix[i][j];
            }
        }
    }
    return dp[0][0];
}
int main()
{
    vector<vector<int> >a;
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
        {
            vector<int>temp;
            for(int j=0;j<m;j++)
            {
                int tmp;
                cin>>tmp;
                temp.push_back(tmp);
            }
            a.push_back(temp);
        }
        cout<<min_path_length(a)<<endl;
    }
    return 0;
}
发表于 2019-10-04 16:20:00 回复(0)
/*
运行时间:953ms

占用内存:43092k
*/
#include <iostream>
#include <vector>
using std::vector;
using std::cin;
using std::cout;
using std::endl;

class solution {
private:
    int n,m;
    vector<int> map; // 将二维数组一维化
public:
    solution(/* args */);
    solution(int n, int m, vector<int> & map):map(map),n(n),m(m) {}
    void output();
    int find_min();
    void init(); // 计算左、下边界上的最短路径
    ~solution();
};

inline int min(int a, int b);

solution::solution(/* args */){
}

solution::~solution() {
}

int solution::find_min() 
{
    init();
    // 从左下向上依次更新(0,0)到该节点的最短路径
    for (size_t i = 1; i < n; i++) {
        for (size_t j = 1; j < m; j++) {
            map[i*m+j] += min(map[(i-1)*m+j], map[i*m+j-1]);
        }
    }
    return map[n*m-1];
}

void solution::output() {
    cout << find_min() << endl;
}

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

void solution::init() {
    for (size_t i = 1; i < m; i++)
    {
        map[i] += map[i-1];
    }

    for (size_t i = 1; i < n; i++)
    {
        map[i*m] += map[(i-1)*m];
    }
}

void input(int &n, int &m, vector<int> & map) {
    cin >> n >> m;
    map.resize(n*m);
    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < m; j++) {
            cin >> map[i*m+j];
        }
    }

}

int main(int argc, char* argv[]) {
    int n,m;
    vector<int> map;
    input(n, m, map);
    solution s(n, m, map);
    s.output();
    return 0;
}
编辑于 2019-09-02 21:24:24 回复(0)

常规的动态规划

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int main(){
    int m, n;
    cin >> m >> n;
    vector<vector<int>> matrix(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            cin >> matrix[i][j];
        }
    }

    vector<vector<int>> sum_matrix(m + 1, vector<int>(n + 1, INT_MAX));
    sum_matrix[1][1] = matrix[0][0];
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if (i == 0 && j == 0)
                continue;
            int idx = i + 1;
            int idy = j + 1;
            sum_matrix[idx][idy] = matrix[i][j] + min(sum_matrix[idx - 1][idy], sum_matrix[idx][idy - 1]);
        }
    }
    cout << sum_matrix[m][n] << endl;
    return 0;
}
发表于 2019-08-28 23:08:07 回复(1)
def shortestRoadSum(arr, n, m):
    #生成n行m列的0矩阵dp
    dp = [[0 for i in range(m)] for j in range(n)]
    dp[0][0] = arr[0][0]
    for i in range(1, n):
        #第一列只能由上向下走
        dp[i][0] = dp[i-1][0] + arr[i][0]
    for j in range(1, m):
        #第一行只能由左向右走
        dp[0][j] = dp[0][j-1] + arr[0][j]
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j]
    return dp[n-1][m-1]

n, m = map(int, input().split())
#输入二维矩阵
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
print(shortestRoadSum(arr, n, m))
python在输入二维矩阵时不用先生成全是0的空矩阵了,否则会超时
求最短路径和还可以优化,待完善!
空间复杂度为O(1)的来了:
def shortestPathSum(arr, n, m):
    #直接修改arr
    for i in range(1, n):
        #第一列只能由上向下走
        arr[i][0] = arr[i-1][0] + arr[i][0]
    for j in range(1, m):
        #第一行只能由左向右走
        arr[0][j] = arr[0][j-1] + arr[0][j]
    for i in range(1, n):
        for j in range(1, m):
            arr[i][j] = min(arr[i-1][j], arr[i][j-1]) + arr[i][j]
    return arr[n-1][m-1]
n, m = map(int, input().split())
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
print(shortestPathSum(arr, n, m))
牛客的是否ac可能和网速和服务器有关,不稳定,同时python与其他语言比起来,运行时间确实算长的,毕竟是解释型语言,感觉每次都走在超时的边缘

运行最快的来了:
def shortestRoadSum(arr, n, m):
    # 每次只保留一行结果
    dp = arr[0]
    # 更新第一行的结果
    for j in range(1, m):
        # 第一行只能由左向右走
        dp[j] += dp[j - 1]
    for i in range(1, n):
        dp[0] += arr[i][0] #每一行开始遍历时更新第一个元素
        for j in range(1, m):
            dp[j] = min(dp[j-1],dp[j]) + arr[i][j]
    return dp[-1]

n, m = map(int, input().split())
# 输入二维矩阵
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
print(shortestRoadSum(arr, n, m))
使用一维矩阵来保存每一行的最优结果,想明白的感觉真好

编辑于 2019-08-14 11:11:36 回复(1)
为啥只能过65%啊,哭辽

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] nums = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                nums[i][j] = sc.nextInt();
            }
        }
        int[][] dp = new int[n][m];
        dp[0][0] = nums[0][0];
        for(int i=1;i<n;i++){
            dp[i][0] = nums[i][0] + dp[i-1][0];
        }
        for(int i=1;i<m;i++){
            dp[0][i] = nums[0][i] + dp[0][i-1];
        }
        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]) + nums[i][j];
            }
        }
        System.out.println(dp[n-1][m-1]);
    }
}


发表于 2019-08-09 11:56:48 回复(1)