公司主营业务网站建设,吴江网页制作,工商局网站怎么做增项,下载网站怎么下载题目 给定一个二维数组matrix[][]#xff0c;一个人必须从左上角出发#xff0c;最终到达右下角#xff0c;沿途只可以向下或者向右走#xff0c;沿途的数字都累加就是距离累加和。返回最小距离累加和。 这道题中会采用压缩数组的算法来进行优化
暴力递归 暴力递归方法的整…题目 给定一个二维数组matrix[][]一个人必须从左上角出发最终到达右下角沿途只可以向下或者向右走沿途的数字都累加就是距离累加和。返回最小距离累加和。 这道题中会采用压缩数组的算法来进行优化
暴力递归 暴力递归方法的整体思路是根据小人所在的位置当前值通过向下传递向左走向右走来获取最终选择路径的最小值。 所以base case可以确定
如果小人走到了最后一行那么接下来就只能向下走。如果小人走到了最后一列那么接下来就只能向左走。如果小人走到了matrix[][]的最后一个格子返回当前值给上层做处理取最小值。否则既可以向左也走可以向右走并获取最小值。
所以暴力递归的方法就出来了。
public static int minPathSum1(int[][] matrix) {if (null matrix || matrix.length 0 || matrix[0] null || matrix[0].length 0) {return -1;}int row matrix.length;int col matrix[0].length;return process(row - 1, col - 1, 0, 0, matrix);}//返回 matrix[i...][j....] 位置的最小值。public static int process(int row, int col, int curRow, int curCol, int[][] matrix) {//当走到最后一个位置返回matrix中最后一个位置的值if (curRow row curCol col) {return matrix[row][col];}//走到最后一行只能往右走只能向右累加if (curRow row) {return matrix[curRow][curCol] process(row, col, curRow, curCol 1, matrix);}//走到最后一列只能向下走if (curCol col) {return matrix[curRow][curCol] process(row, col, curRow 1, curCol, matrix);}//否则可以向右走可以向下走进行累加。int curValue matrix[curRow][curCol];int p1 curValue process(row, col, curRow 1, curCol, matrix);int p2 curValue process(row, col, curRow, curCol 1, matrix);return Math.min(p1, p2);}动态规划 这道题的动态规划也不难给定的是一个二维数组matrix[][]每次行和列会进行变化可变参数,所以可以创建一个和matrix大小相等的dp[][]来存放每一步计算的值。 因为只可以向下走或向右走所以dp中任选一个格子的依赖是依赖自己的左侧的值和上面的值。其中dp中第一行的值只会依赖同行左侧的值dp中第一列的值只会依赖同一列上面的值。 所以先将dp中第一行和第一列的值填充好后其余的按照依赖关系填充即可完善dp表。
代码 public static int dp(int[][] matrix) {if (null matrix || matrix.length 0 || matrix[0] null || matrix[0].length 0) {return -1;}int row matrix.length;int col matrix[0].length;int[][] dp new int[row][col];dp[0][0] matrix[0][0];for (int i 1; i col; i) {dp[0][i] dp[0][i - 1] matrix[0][i];}for (int j 1; j row; j) {dp[j][0] dp[j - 1][0] matrix[j][0];}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]) matrix[i][j];}}return dp[row - 1][col - 1];}优化 动态规划方法中是创建了一个和matrix[][]大小相等的dp表通过填充dp表来完善的代码。
如果给定的matrix[][]太大了是不是我的dp表也要跟着很大并且在填充dp表时第三行依赖第二行的值第四行依赖第三行的值此时。第二行的值就已经没有用了不再需要它了所以是不是只需要一个跟matrix[][]中列的长度相等的一维数组arr[]就够了。 代码 public static int minPathSum2(int[][] matrix) {if (matrix null || matrix.length 0 || matrix[0] null || matrix[0].length 0) {return 0;}int row matrix.length;int col matrix[0].length;int[] arr new int[col];arr[0] matrix[0][0];//根据matrix第一行的值填充arrfor (int i 1; i col; i) {arr[i] arr[i - 1] matrix[0][i];}for (int i 1; i row; i) {arr[0] matrix[i][0];for (int j 1; j col; j) {//arr[j - 1] : 相当于我依赖的左边//arr[j] : 因为此时arr[j]的值还没修改还是上一行的值相当于自己的上面。 arr[j] Math.min(arr[j - 1], arr[j]) matrix[i][j];}}return arr[col - 1];}
