蓝桥杯DP算法最小路径和

最小路径和
给定一个包含非负数整数的m*n网格，请找出一条从左上角到右下角的路径，
使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

输入样例
3 3
1 3 1
1 5 1
4 2 1
输出样例
7

代码实现

package PC;
import java.util.Scanner;
public class dome5 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m
= sc.nextInt();
int n =sc.nextInt();
int [][] a = new int[m][n];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
a[i][j]=sc.nextInt();
}
}
int [][]dp = new int [m][n];
dp[0][0] = a [0][0];//起点
for (int i = 1; i < m; i++)dp[0][i]= dp[0][i-1]+a[0][i];//向右走
for (int i = 1; i < n; i++)dp[i][0]= dp[i-1][0]+a[i][0];//向下走
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp.length; j++) {
dp[i][j]= Math.min(dp[i][j-1],dp[i-1][j] )+a[i][j];//两种走法那个和小
}
}
System.out.println(dp[m-1][n-1]);
}
}

最后

以上就是风趣芒果为你收集整理的蓝桥杯DP算法最小路径和的全部内容，希望文章能够帮你解决蓝桥杯DP算法最小路径和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。