1.最小路径和（64 - 中）
题目描述：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 :
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
思路：典型动态规划，定义dp数组记录累加值，状态转移方程为：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。
代码实现：
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for(int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
空间优化：空间复杂度O(n)，滚动数组：因为i行依赖i行和i - 1行，所以我们计算完i行覆盖i - 1行的值，不会对最终结果。
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] dp = new int[n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (j == 0) { // 只能从上边界来
dp[j] = dp[j];
} else if (i == 0) { // 只能从左边界来
dp[j] = dp[j - 1];
} else {
dp[j] = Math.min(dp[j - 1], dp[j]);
}
dp[j] += grid[i][j];
}
}
return dp[n - 1];
}
2.不同路径（62 - 中）
题目描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 :
输入：m = 3, n = 7
输出：28
思路：典型动态规划问题，与上题不同的是dp数组记录的是到达该点的路径总数，状态转移方程为：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。注意dp数组初始值为1，即到达该位置的路径为1.
代码实现：
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; ++i) {
dp[i][0] = 1;
}
for (int j = 0; j < n; ++j) {
dp[0][j] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
空间优化：空间复杂度O(min(m, n))，同理。
public int uniquePaths(int m, int n) {
int less = Math.min(m, n), more = Math.max(m, n);
int[] dp = new int[less];
Arrays.fill(dp, 1);
for (int i = 1; i < more; ++i) {
for (int j = 1; j < less; ++j) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[less - 1];
}
3.不同路径II（63 - 中）
题目描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
现在考虑网格中有障碍物。问总共有多少条不同的路径？
示例 :
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
思路：与上题类似，注意更新dp数组进行判断，该点如果是障碍则跳过。注意：本题不能进行空间压缩。
代码实现：
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
// 处理边界条件
for (int i = 0; i < m && obstacleGrid[i][0] == 0; ++i) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; ++j) dp[0][j] = 1;
// 顺序填表
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
//当前位置为障碍物
if (obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
拓展：三角形最小路径和（120 - 中）
题目描述：给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 :
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
思路：动态规划，dp数组：到达某层的最小路径和，由题意的依赖关系，转移方程应为：dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j)，即从下向上填表。注意：由于i依赖于i和i + 1，所以外层循环要倒叙，空间压缩时防止覆盖。
代码实现：
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n + 1];
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
拓展：圆环回原点问题（字节高频题）
题目描述：圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。举例：
- 如果n=1，则从0出发只能到1或者9，不可能回到0，共0种走法
- 如果n=2，则从0出发有4条路径:0->1->2, 0->1->0, 0->9->8, 0->9->0,其中有两条回到了0点，故一共有2种走法
示例：
输入: 2
输出: 2
解释：有2种方案。分别是0->1->0和0->9->0
思路：本题考察点是动态规划，与Leetcode70爬楼梯相似。
-
dp[i][j]为从0点出发走i步到j点的方案数 - 状态转移方程：走
n步到0的方案数=走n-1步到1的方案数+走n-1步到9的方案数（j步达到i点的问题，转化为j-1步从相邻的两个节点到达目标节点的方法数之和）。即dp[i][j] = dp[i - 1][(j - 1 + n) % n] + dp[i - 1][(j + 1) % n] - ps:公式之所以取余是因为
j-1或j+1可能会超过圆环0~9的范围。
代码：
import java.util.Scanner;
public class Solution005 {
public static void main(String[] args) {
System.out.println("请输入圆环节点个数和步数n：");
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int n = sc.nextInt();
System.out.println(solution(length, n));
}
public static int solution(int n, int k) {
if (n == 0) {
return 1;
}
// 只有两个环，偶数步数有一种方案，奇数步数不能到达
if (n == 2) {
if (k % 2 == 0) {
return 1;
} else {
return 0;
}
}
// dp[i][j]为从0点出发走i步到j点的方案数
int[][] dp = new int[k + 1][n];
dp[0][0] = 1;
// 0步到达任何位置(除0)的方法数为0，java可省略
for (int j = 1; j < n; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= k; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][(j - 1 + n) % n] + dp[i - 1][(j + 1) % n];
}
}
return dp[k][0];
}
}
拓展：如果本题不是返回原点，而是k步到达3这个点的方法总数，只需要返回 dp[k][3] 即可。
拓展：交错字符串（97-中）
题目描述：给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。每个字符串被分成长度若干的子串，验证这些子串是否可以交错拼接 s3。
示例：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true
s3 = aa ddbc bc a c
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false
s3不能由s1和s2交错组成。
思路：参考@sage大佬，上图
问题转化为：每次只能向右或者向下选择字符，问是否存在target路径。注意当len(s1) + len(s2) != len(s3)时一定不能交错匹配，否则进行动态规划求解：
-
dp[i][j]代表 s1 前 i 个字符与 s2 前 j 个字符拼接成 s3 的 i+j 字符，也就是存在目标路径能够到达 i ,j ； - 状态转移方程：到达(i, j)可能由上边位置过来或者左边位置过来
ps：边界条件注意，字符串都为空，返回true；
代码：
public boolean isInterleave(String s1, String s2, String s3) {
int n1 = s1.length(), n2 = s2.length();
if (s3.length() != n1 + n2) {
return false;
}
// dp[i,j]表示s1前i字符能与s2前j字符组成s3前i+j个字符；
boolean[][] dp = new boolean[n1 + 1][n2 + 1];
dp[0][0] = true;
for (int i = 1; i <= n1 && s1.charAt(i - 1) == s3.charAt(i - 1); i++) dp[i][0] = true;
for (int j = 1; j <= n2 && s2.charAt(j - 1) == s3.charAt(j - 1); j++) dp[0][j] = true;
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
|| dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
}
}
return dp[n1][n2];
}
网友评论