Leetcode --- 矩阵路径问题（动态规划）

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