给出一个二维数组，一个人从左上角出发，最终到达右下角，沿途数字累积，求返回最小的累加和

问题描述：给出一个二维数组arr，一个人从左上角出发，沿途只能向下或向左走，并且沿途的数数字都累加，最终到达右下角，求返回最小的累加和

举例:给出一个数组    int[][] arr = new int[][]{{3, 7,8,7}, {1, 2,6,4},{10,3,8,9},{8,1,2,0}};

需求是返回 12

解决思想：动态规划的解决方案，此处提供两个方案，一种是常规方案，另一种是节约内存的方案。

1、常规方案：

1.1、分析图如下：

人从左上角3的位置开始移动，每次只能向左或向右移动一步，到右下角0结束，找到过程最小值 12

此路径的值最小，为12 

1.2、核心代码如下：

/*** @author wanghuainan* @date 2021/7/5 10:28*/
public class NanDaoMinPathSum {public static void main(String[] args) {//     int[][] arr = new int[10][10];int[][] arr = new int[][]{{3, 7,8,7}, {1, 2,6,4},{10,3,8,9},{8,1,2,0}};//  arr = new int[][]{{2, 3}, {1, 1}};System.out.println(minSumPath1(arr));}private static int minSumPath1(int[][] arr) {//边界判断if(arr.length == 0 || arr == null || arr[0] == null || arr[0].length == 0){return 0;}int row = arr.length;int col = arr[0].length;int[][] dp = new int[row][col];//定义一个缓存数组dp[0][0] = arr[0][0];//左上角赋值//第一列赋值for(int i = 1;i < row;i++){dp[i][0] = dp[i - 1][0] + arr[i][0];}//第一行赋值for(int j = 1;j < col;j++){dp[0][j] = dp[0][j - 1] + arr[0][j];}//中间其他行列格子里赋最小值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]) + arr[i][j];}}return dp[row - 1][col -1];//返回右下角的值}
}

2、节约内存的方案（此处按行计算，当然也可以按照列计算）：

2.1、图示分析：

采用一维数组，？处的值是通过14或6中先取最小值，然后加上3，即值为9 

2.2、核心代码

/*** @author wanghuainan* @date 2021/7/5 10:28*/
public class NanDaoMinPathSum {public static void main(String[] args) {//     int[][] arr = new int[10][10];int[][] arr = new int[][]{{3, 7,8,7}, {1, 2,6,4},{10,3,8,9},{8,1,2,0}};//  arr = new int[][]{{2, 3}, {1, 1}};System.out.println(minSumPath2(arr));}private static int minSumPath2(int[][] arr) {if(arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0){return 0;}int row = arr.length;int col = arr[0].length;int[] dp = new int[col];//一维数组，仅保存一行有效数据，节约内存dp[0] = arr[0][0];//初始化第一行数据for(int j = 1;j < col;j++){dp[j] = dp[j - 1] + arr[0][j];}for(int i = 1;i < row; i++){dp[0] +=arr[i][0];for(int j = 1;j < col;j++){//得出数组中j位置的数值，左边dp[j]代表j位置最新数值，右边dp[j]代表上一行历史数据，加上m[i][j]后得到j处最新数值dp[j] = Math.min(dp[j - 1],dp[j]) + arr[i][j];}}return dp[col - 1];}}

3、两种方案的执行结果：

到此，此算法的解决方案分享完毕，这到算法算是比较简单的问题，大家一定要多多联系，定会进步很快！