矩阵的最小路径和

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));
    }
}

#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;
}

#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;
}

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];
}

#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;
}

#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;
}

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];
    }
}

#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);
}

//参考别人的
#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;
	
}

根据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;
}

/*
运行时间：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;
}

常规的动态规划

#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;
}

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))

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))

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))