[LanQao]矩阵的最小路径和 dp 经典

10
2019/08

# [LanQao]矩阵的最小路径和 dp 经典

## 题目大意

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

## 代码

### wa dfs

package BlueCup.Seven_recursion.Test;

import java.util.Scanner;

public class 矩阵的最小路径和 {
static int a[][];
static int m, n;

public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
m = cin.nextInt();
n = cin.nextInt();
a = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = cin.nextInt();
}
}
dfs(0, 0);
System.out.println(sum);
}

static int sum = 0;

private static void dfs(int x, int y) {
sum += a[x][y];
if (x == m - 1 || y == n - 1) {
return;
}
if (a[x + 1][y] > a[x][y + 1]) {
dfs(x, y + 1);
} else {
dfs(x + 1, y);
}
}
}

### AC DP

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

package BlueCup.Seven_recursion.Test;

import java.util.Scanner;

public class 矩阵的最小路径和 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] a = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = sc.nextInt();
}
}
for (int i = 1; i < n; i++) {
a[i][0]+=a[i-1][0];
}
for (int i = 1; i < m; i++) {
a[0][i]+=a[0][i-1];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
a[i][j] += Math.min(a[i - 1][j], a[i][j - 1]) ;
}
}
System.out.println(a[n - 1][m - 1]);
}
}

### 类似的题

{ 0 0 7 0 0，

0 0 0 5 0,

2 0 4 0 0,

0 0 0 3 0},

### oj

百度已收录

Last modification：August 10th, 2019 at 02:59 pm