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]; }
