本文共 5508 字，大约阅读时间需要 18 分钟。

三角矩阵(Triangle)

• 题目描述:
  链接：
  来源：牛客网

给出一个三角形，计算从三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字，

例如，给出的三角形如下： [[2],[3,4],[6,5,7],[4,1,8,3]] 最小的从顶部到底部的路径和是2 + 3 + 5 + 1 = 11。

• 解题思路
  
• 方法一代码

/**     * 三角矩阵     * @param triangle     * @return     */    public int minimumTotal(ArrayList
   
    
     > triangle) {
           if (triangle == null) return 0;        if (triangle.isEmpty()) return 0;        if (triangle.size() == 1) return triangle.get(0).get(0); //只有一行数据的时候        //row表示行        for (int row = 1; row < triangle.size(); row++) {
               //col表示列            for (int col = 0; col < triangle.get(row).size(); col++) {
                   if (col == 0) {
                       //第一个, 直接加上一行第一个就行                    triangle.get(row).set(col, triangle.get(row - 1).get(0) + triangle.get(row).get(0));                } else if (col == row) {
                       //每一行最后一个数据                    triangle.get(row).set(col, triangle.get(row - 1).get(row - 1) + triangle.get(row).get(col));                } else {
                       triangle.get(row).set(col, Math.min(triangle.get(row - 1).get(col - 1), triangle.get(row - 1).get(col))                            + triangle.get(row).get(col));                }            }        }        //返回最后一行的最小的那个数字        ArrayList
     
       numList = triangle.get(triangle.size() - 1);        int ret = numList.get(0);        for (int i = 1; i < numList.size(); i++) {
               ret = Math.min(ret, numList.get(i));        }        return ret;    }
     
    
   

• 方法二代码

public int minimumTotal2(ArrayList
   
    
     > triangle) {
           if (triangle == null) return 0;        if (triangle.isEmpty()) return 0;        if (triangle.size() == 1) return triangle.get(0).get(0); //只有一行数据的时候        for (int row = triangle.size() - 1 - 1; row >= 0; row--) {
               for (int col = 0; col < row + 1; col++) {
                   triangle.get(row).set(col, Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1))                        + triangle.get(row).get(col));            }        }        return triangle.get(0).get(0);    }
    
   

路径总数(Unique Paths)

• 问题描述
  链接：
  来源：牛客网

一个机器人在m×n大小的地图的左上角（起点，下图中的标记“start"的位置）。

机器人每次向下或向右移动。机器人要到达地图的右下角。（终点，下图中的标记“Finish"的位置）。 可以有多少种不同的路径从起点走到终点？ 上图是3×7大小的地图，有多少不同的路径？ 备注：m和n小于等于100

• 解题思路
  
• 代码

/**     * 路径总数(Unique Paths)     * @param "m行数"     * @param "n列数"     * @return     */    public int uniquePaths(int m, int n) {
           if (m == 0 || n== 0) return 0;        //构建二维数组        int[][] answers = new int[m][n];        //将第一行和第一列初始化为1        for (int i = 0; i < n; i++) {
               answers[0][i] = 1;        }        for (int i = 0; i < m; i++) {
               answers[i][0] = 1;        }        //从第二行第二列开始动态计算        for (int row = 1; row < m; row++) {
               for (int col = 1; col < n; col++) {
                   answers[row][col] = answers[row - 1][col] + answers[row][col - 1];            }        }        return answers[m - 1][n - 1];    }

路径总数2(Unique Paths II)

• 题目描述
  链接：
  来源：牛客网

继续思考题目"Unique Paths":

如果在图中加入了一些障碍，有多少不同的路径？ 分别用0和1代表空区域和障碍 例如 下图表示有一个障碍在3*3的图中央。 [ [0,0,0], [0,1,0], [0,0,0] ] 有2条不同的路径 备注：m和n不超过100.

• 解题思路
  
• 代码

/**     * 带权路径总数(Unique Paths II)     * @param obstacleGrid     * @return     */     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
           if (obstacleGrid == null) return 0;        if (obstacleGrid.length == 0) return 0;        if (obstacleGrid[0].length == 0) return 0;        //构建二维数组         int[][] answers = new int[obstacleGrid.length][obstacleGrid[0].length];         //第一行和第一列的设置         for (int col = 0; col < obstacleGrid[0].length; col++) {
                if (obstacleGrid[0][col] == 1) {
                    //遇到1表示走不通, 退出循环                 break;             } else {
                    answers[0][col] = 1;             }         }         for (int row = 0; row < obstacleGrid.length; row++) {
                if (obstacleGrid[row][0] == 1) {
                    break;             } else {
                    answers[row][0] = 1;             }         }         //从第二行第二列开始算起         for (int row = 1; row < obstacleGrid.length; row++) {
                for (int col = 1; col < obstacleGrid[0].length; col++) {
                    if (obstacleGrid[row][col] == 1) {
                        answers[row][col] = 0;                 } else {
                        answers[row][col] = answers[row - 1][col] + answers[row][col - 1];                 }             }         }         return answers[obstacleGrid.length - 1][obstacleGrid[0].length - 1];     }

最小路径和(Minimum Path Sum)

• 问题描述
  题目描述：
  给定一个m*n的网格，网格用非负数填充，找到一条从左上角到右下角的最短路径。
  注：每次只能向下或者向右移动。
  
  方法：动态规划
• 解题思路
  
• 代码

/**     * 最小路径和(Minimum Path Sum)     * @param grid     * @return     */     public int minPathSum(int[][] grid) {
            if (grid == null) return 0;         if (grid.length == 0) return 0;         if (grid[0].length == 0) return 0;         //第一行和第一列数据 形成累加         for (int row = 1; row < grid.length; row++) {
                grid[row][0] += grid[row - 1][0];         }         for (int col = 1; col < grid[0].length; col++) {
                grid[0][col] += grid[0][col - 1];         }         //从第二行第二列开始运算         for (int row = 1; row < grid.length; row++) {
                for (int col = 1; col < grid[0].length; col++) {
                    grid[row][col] = Math.min(grid[row - 1][col], grid[row][col - 1])                         + grid[row][col];             }         }         return grid[grid.length - 1][grid[0].length - 1];     }

转载地址：http://jjsci.baihongyu.com/