第五题 三角矩阵

题目链接

题目描述

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

[[20],[30,40],[60,50,70],[40,10,80,30]]

最小的从顶部到底部的路径和是20 + 30 + 50 + 10 = 110。 注意： 如果你能只用O（N）的额外的空间来完成这项工作的话，就可以得到附加分，其中N是三角形中的行总数。

解题思路一

方法：动态规划 问题：从（0，0）到达最后一行的最小路径和 子状态：从(0,0)到(1,0),(1,1),(2,0),…(n,n)的最短路径和 F(i,j): 从(0,0)到(i,j)的最短路径和 状态递推： F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j] 对于边界需要特殊考虑; F(i,0) = F(i-1, 0)+triangle(i, 0)) F(i,i) = F(i-1, j-1)+triangle(i, i)) 初始值： F(0,0) = triangle[0][0] 返回结果： min(F(n-1, i))

实现代码

package java_20201001; import java.util.ArrayList; import java.util.List; /** * @ Created with IntelliJ IDEA. * @ClassName Test1 * @Description * @Author by小房 * @Date 2020/10/1 19:50 */ public class Test1 { public class Solution { public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { if (triangle.isEmpty()) { return 0; } List<List<Integer>> minPathSum = new ArrayList<>(); for (int i = 0; i < triangle.size(); ++i) { minPathSum.add(new ArrayList<>()); } minPathSum.get(0).add(triangle.get(0).get(0)); for (int i = 1; i < triangle.size(); i++) { int curSum = 0; for (int j = 0; j <= i; j++) { if (j == 0) { curSum = minPathSum.get(i-1).get(0); } else if (j == i) { curSum = minPathSum.get(i - 1).get(j - 1); } else { curSum = Math.min(minPathSum.get(i - 1).get(j), minPathSum.get(i - 1).get(j - 1)); } minPathSum.get(i).add(triangle.get(i).get(j) + curSum); } } int size = triangle.size(); int allMin = minPathSum.get(size - 1).get(0); for (int i = 1; i < size; i++) { allMin = Math.min(allMin, minPathSum.get(size -1).get(i)); } return allMin; } } }

解题思路二（反向思维）

状态： 子状态：从(n,n),(n,n-1),…(1,0),(1,1),(0,0)到最后一行的最短路径和 F(i,j): 从(i,j)到最后一行的最短路径和 状态递推： F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j] 初始值： F(n-1,0) = triangle[n-1][0], F(n-1,1) = triangle[n-1][1],…, F(n-1,n-1) = triangle[n-1][n-1] 返回结果： F(0, 0) 这种逆向思维不需要考虑边界，也不需要最后寻找最小值，直接返回F(0,0)即可

代码实现

package java_20201006; import java.util.ArrayList; import java.util.List; /** * @ Created with IntelliJ IDEA. * @ClassName Test1 * @Description * @Author by小房 * @Date 2020/10/6 19:57 */ public class Test1 { public class Solution { public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { if (triangle.isEmpty()) { return 0; } ArrayList<ArrayList<Integer>> minPathSum = new ArrayList<>(triangle); int row = triangle.size(); for (int i = row - 2; i >= 0 ; --i) { int temp = 0; for (int j = 0; j <= i ; j++) { temp = Math.min(minPathSum.get(i + 1).get(j), minPathSum.get(i + 1).get(j + 1)); minPathSum.get(i).add(temp + minPathSum.get(i).get(j)); } } return minPathSum.get(0).get(0); } } }

总结：

/* 注： 易错点：只保留每一步的最小值，忽略其他路径，造成最终结果错误 局部最小不等于全局最小 总结： 遇到关于矩阵，网格，字符串间的比较，匹配的问题， 单序列(一维)动规解决不了的情况下， 就需要考虑双序列(二维)动规 */

第六题 路径总数(Unique Paths)

题目链接

题目描述

一个机器人在m×n大小的地图的左上角（起点，下图中的标记“start"的位置）。 机器人每次向下或向右移动。机器人要到达地图的右下角。（终点，下图中的标记“Finish"的位置）。 可以有多少种不同的路径从起点走到终点？

上图是3×7大小的地图，有多少不同的路径？ 备注：m和n小于等于100

解题思路

方法：动态规划 状态： 子状态：从(0,0)到达(1,0),(1,1),(2,1),…(m-1,n-1)的路径数 F(i,j): 从(0,0)到达F(i,j)的路径数 状态递推： F(i,j) = F(i-1,j) + F(i,j-1) 初始化： 特殊情况：第0行和第0列 F(0,i) = 1 F(i,0) = 1 返回结果： F(m-1,n-1)

代码实现

import java.util.*; public class Solution { /** * * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { // write code here int[][] array = new int[m][n]; for (int i = 0; i <= m -1; i++) { for (int j = 0; j <= n -1 ; j++) { array[i][j] = 1; } } for (int i = 1; i <= m -1; i++) { for (int j = 1; j <= n -1 ; j++) { array[i][j] = array[i -1][j] + array[i][j-1]; } } return array[m-1][n-1]; } }

第7题 路径总数(Unique Paths II)

题目链接

题目描述

继续求路径。 如果在图中加入了一些障碍，有多少不同的路径？ 分别用0和1代表空区域和障碍 例如 下图表示有一个障碍在3*3的图中央。

[ [0,0,0], [0,1,0], [0,0,0] ]

有2条不同的路径 备注：m和n不超过100.

解题思路

方法：动态规划 状态： 子状态：从(0,0)到达(1,0),(1,1),(2,1),…(m-1,n-1)的路径数 F(i,j): 从(0,0)到达F(i,j)的路径数 状态递推： F(i,j) = {F(i-1,j) + F(i,j-1)} OR {0, if obstacleGrid(i,j) = 1} 初始化： 特殊情况：第0行和第0列 F(0,i) = {1} OR {0, if obstacleGrid(0,j) = 1, j <= i} F(i,0) = {1} OR {0, if obstacleGrid(j,0) = 1, j <= i} 返回结果： F(m-1,n-1)

代码实现

import java.util.*; public class Solution { /** * * @param obstacleGrid int整型二维数组 * @return int整型 */ public int uniquePathsWithObstacles (int[][] obstacleGrid) { // write code here int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] array = new int[m][n]; int tmp = 1; for (int i = 0; i <= m -1; i++) { if (obstacleGrid[i][0] ==1) { tmp = 0; } array[i][0] = tmp; } tmp = 1; for (int i = 0; i <= n -1; i++) { if (obstacleGrid[0][i] ==1) { tmp = 0; } array[0][i] = tmp; } for (int i = 1; i <= m -1; i++) { for (int j = 1; j <= n -1 ; j++) { if (obstacleGrid[i][j] == 1) { array[i][j] = 0; } else { array[i][j] = array[i -1][j] + array[i][j-1]; } } } return array[m-1][n-1]; } }

第8题 最小路径和(Minimum Path Sum)

题目链接

题目描述

给定一个由非负整数填充的m x n的二维数组，现在要从二维数组的左上角走到右下角，请找出路径上的所有数字之和最小的路径。 注意：你每次只能向下或向右移动。

解题思路

方法：动态规划 状态： 子状态：从(0,0)到达(1,0),(1,1),(2,1),…(m-1,n-1)的最短路径 F(i,j): 从(0,0)到达F(i,j)的最短路径 状态递推： F(i,j) = min{F(i-1,j) , F(i,j-1)} + (i,j) 初始化： F(0,0) = (0,0) 特殊情况：第0行和第0列 F(0,i) = F(0,i-1) + (0,i) F(i,0) = F(i-1,0) + (i,0) 返回结果： F(m-1,n-1)

代码实现

import java.util.*; public class Solution { /** * * @param grid int整型二维数组 * @return int整型 */ public int minPathSum (int[][] grid) { // write code here if (grid.length == 0) { return 0; } int row = grid.length; int col = grid[0].length; for (int i = 1; i < row; i++) { grid[i][0] += grid[i-1][0]; } for (int i = 1; i < col; i++) { grid[0][i] += grid[0][i-1]; } for (int i = 1; i < row ; i++) { for (int j = 1; j < col; j++) { grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j]; } } return grid[row-1][col-1]; } }