DP - 路径问题

☆☆☆62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6

提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //当前位置可以由向下和向右移动到
                else if (i > 0)
                    dp[i][j] = dp[i - 1][j];    //当前位置只能由向下移动到
                else if (j > 0)
                    dp[i][j] = dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1)
            return 0;

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 对于有障碍物的格子，则有f[i][j] = 0，因此这里选择不更新有障碍物的格子
                if (obstacleGrid[i][j] != 1) {
                    if (i > 0 && j > 0)
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    else if (i > 0)
                        dp[i][j] = dp[i - 1][j];
                    else if (j > 0)
                        dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0)
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                else if (i > 0)
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                else if (j > 0)
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 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）。
示例 2：
输入：triangle = [[-10]]
输出：-10

提示：
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

进阶：
你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int lines = triangle.size();
        int[] dp = new int[lines];
        dp[0] = triangle.get(0).get(0);

        for (int i = 1; i < lines; i++) {
            List<Integer> nowLine = triangle.get(i);
            for (int j = i; j >= 0; j--) {
                if (j == i)
                    dp[j] = dp[j - 1] + nowLine.get(j);
                else if (j == 0)
                    dp[j] = dp[j] + nowLine.get(j);
                else dp[j] = Math.min(dp[j], dp[j - 1]) + nowLine.get(j);
            }
        }
        return Arrays.stream(dp).min().getAsInt();
    }
}

931. 下降路径最小和

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗+斜体标注：
[[2,1,3], [[2,1,3],
[6,5,4], [6,5,4],
[7,8,9]] [7,8,9]]
示例 2：
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57],
[-40,-5]]
示例 3：
输入：matrix = [[-48]]
输出：-48

提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        if (n == 1)
            return matrix[0][0];

        int[][] dp = new int[n + 1][n];

        for (int i = 1; i <= n; i++) {
            int[] num = matrix[i - 1];
            for (int j = 0; j < n; j++) {
                if (j == 0)
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + num[j];
                else if (j == n - 1)
                    dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + num[j];
                else
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + num[j];
            }
        }

        return Arrays.stream(dp[n]).min().getAsInt();
    }
}

1289. 下降路径最小和 II

给你一个整数方阵 arr ，定义「非零偏移下降路径」为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
请你返回非零偏移下降路径数字和的最小值。

示例 1：
输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。

提示：
1 <= arr.length == arr[i].length <= 200
-99 <= arr[i][j] <= 99

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int m = grid.length;    //行
        int n = grid[0].length; //列
        if (n == 1) {
            int result = 0;
            for (int[] num : grid)
                result += num[0];
            return result;
        }

        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++)
            dp[0][i] = grid[0][i];

        for (int i = 1; i < m; i++) {
            int[] nums = grid[i];
            int[] min = findMin(dp[i - 1]);
            for (int j = 0; j < n; j++) {
                if (j != min[1])
                    dp[i][j] = min[0] + nums[j];
                else
                    dp[i][j] = min[2] + nums[j];
            }
        }

        return Arrays.stream(dp[m - 1]).min().getAsInt();
    }

    int[] findMin(int[] arr) {
        int[] min = new int[3]; //min, min_index, second_min
        if (arr[0] < arr[1]) {
            min[0] = arr[0];
            min[2] = arr[1];
        } else {
            min[0] = arr[1];
            min[1] = 1;
            min[2] = arr[0];
        }

        for (int i = 1; i < arr.length; i++) {
            int num = arr[i];
            if (num < min[0]) {
                min[2] = min[0];
                min[0] = num;
                min[1] = i;
            } else if (num < min[2] && i != min[1])
                min[2] = num;
        }
        return min;
    }
}

☆☆☆1575. 统计所有可行路径

给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量
每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。
请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。
请你返回从 start 到 finish 所有可能路径的数目。
由于答案可能很大， 请将它对 10^9 + 7 取余后返回。

示例 1：
输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3
示例 2：
输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
输出：5
解释：以下为所有可能的路径：
1 -> 0，使用汽油量为 fuel = 1
1 -> 2 -> 0，使用汽油量为 fuel = 5
1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
示例 3：
输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
输出：0
解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
示例 4 ：
输入：locations = [2,1,5], start = 0, finish = 0, fuel = 3
输出：2
解释：总共有两条可行路径，0 和 0 -> 1 -> 0 。
示例 5：
输入：locations = [1,2,3], start = 0, finish = 2, fuel = 40
输出：615088286
解释：路径总数为 2615088300 。将结果对 10^9 + 7 取余，得到 615088286 。

提示：
2 <= locations.length <= 100
1 <= locations[i] <= 10^9
所有 locations 中的整数 互不相同 。
0 <= start, finish < locations.length
1 <= fuel <= 200

记忆化搜索

class Solution {
    //cache[i][fuel]代表从位置i出发，当前剩余的油量为fuel的前提下，到达目标位置的「路径数量」
    int[][] cache;
    final int MOD = 1000000007;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        cache = new int[locations.length][fuel + 1];
        //将cache所有元素初始化为-1，表示还没计算过
        for (int[] c : cache)
            Arrays.fill(c, -1);

        return dfs(locations, start, finish, fuel);
    }

    int dfs(int[] locations, int now, int finish, int fuel) {
        //Base case 0: 之前已经计算过了，直接返回
        if (cache[now][fuel] != -1)
            return cache[now][fuel];

        //Base case 1: 如果油量为0
        if (fuel == 0) {
            cache[now][fuel] = now == finish ? 1 : 0;
            return cache[now][fuel];
        }

        //Base case 2: 如果油量不为0
        //计算油量为fuel，从now到finish的路径数量
        int sum = now == finish ? 1 : 0;
        for (int i = 0; i < locations.length; i++) {
            if (i != now) {
                int cost = Math.abs(locations[now] - locations[i]);
                if (fuel >= cost) {
                    sum = (dfs(locations, i, finish, fuel - cost) + sum) % MOD;
                }
            }
        }
        cache[now][fuel] = sum;
        return cache[now][fuel];
    }
}

• 时间复杂度时间复杂度：最坏情况下共有 n fuel 个状态需要计算（填满整个 cachecache 数组）。每计算一个状态需要遍历一次 locations 数组，复杂度为 O(n)。整体复杂度为 O(n^2 fuel)
• 耗时47ms，击败78.7%

记忆化搜索-优化

class Solution {
    //cache[i][fuel]代表从位置i出发，当前剩余的油量为fuel的前提下，到达目标位置的「路径数量」
    int[][] cache;
    final int MOD = 1000000007;

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        cache = new int[locations.length][fuel + 1];
        //将cache所有元素初始化为-1，表示还没计算过
        for (int[] c : cache)
            Arrays.fill(c, -1);

        return dfs(locations, start, finish, fuel);
    }

    int dfs(int[] locations, int now, int finish, int fuel) {
        //Base case 0: 之前已经计算过了，直接返回
        if (cache[now][fuel] != -1)
            return cache[now][fuel];

        //Base case 1: 如果油量为0
        if (fuel == 0) {
            cache[now][fuel] = now == finish ? 1 : 0;
            return cache[now][fuel];
        }

        //Base case 2: 如果油量不为0
        //先计算一步能否到终点再计算油量为fuel，从now到finish的路径数量
        if (Math.abs(locations[now] - locations[finish]) > fuel) {
            cache[now][fuel] = 0;
            return cache[now][fuel];
        }
        int sum = now == finish ? 1 : 0;
        for (int i = 0; i < locations.length; i++) {
            if (i != now) {
                int cost = Math.abs(locations[now] - locations[i]);
                if (fuel >= cost) {
                    sum = (dfs(locations, i, finish, fuel - cost) + sum) % MOD;
                }
            }
        }
        cache[now][fuel] = sum;
        return cache[now][fuel];
    }
}

• 总体时间复杂度不变，但是耗时减少

• 耗时35ms，击败96%

  记忆化搜索改动态规划

  
  

  class Solution {
  public int countRoutes(int[] locations, int start, int finish, int fuel) {
     int n = locations.length;
     //dp[i][fuel]代表从位置i出发，当前剩余的油量为fuel的前提下，到达目标位置的「路径数量」
     int[][] dp = new int[n][fuel + 1];
     final int MOD = 1000000007;
  
     //dp初始化，不管多少油量，在终点的路径均为1
     for (int i = 0; i <= fuel; i++)
         dp[finish][i] = 1;
  
     //动态转移方程为dp[i][fuel] = SUM(dp[k][fuel-need])，其中need为|location[i]-location[k]|
     //从转移方程可以发现，计算dp[i][fuel]依赖于dp[k][fuel-need]，即油量有严格大小关系，而i和k没有
     //因此可以从小到大枚举油量这一维
     for (int f = 1; f <= fuel; f++) {
         for (int now = 0; now < n; now++) {
             for (int end = 0; end < n; end++) {
                 if (now != end) {
                     int need = Math.abs(locations[now] - locations[end]);
                     if (f >= need)
                         dp[now][f] = (dp[now][f] + dp[end][f - need]) % MOD;
                 }
             }
         }
     }
     return dp[start][fuel];
  }
  }
  

☆ 576. 出界的路径数

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。

动态规划

个人分析出dp中的变量为row、column和step
动态规划方程为
dp[i][j][k] = dp[i-1][j][k-1] + dp[i+1][j][k-1] + dp[i][j-1][k-1] + dp[i][j+1][k-1]

class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0)
            return 0;
        final int MOD = 1000000007;
        int[][][] dp = new int[maxMove + 1][m][n];
        //dp初始化，网格四周的格子到网络外的路径为1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0)
                    dp[1][i][j]++;
                if (i == m - 1)
                    dp[1][i][j]++;
                if (j == 0)
                    dp[1][i][j]++;
                if (j == n - 1)
                    dp[1][i][j]++;
            }
        }

        for (int step = 1; step <= maxMove; step++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != 0)
                        dp[step][i][j] = (dp[step - 1][i - 1][j] + dp[step][i][j]) % MOD;
                    if (i != m - 1)
                        dp[step][i][j] = (dp[step - 1][i + 1][j] + dp[step][i][j]) % MOD;
                    if (j != 0)
                        dp[step][i][j] = (dp[step - 1][i][j - 1] + dp[step][i][j]) % MOD;
                    if (j != n - 1)
                        dp[step][i][j] = (dp[step - 1][i][j + 1] + dp[step][i][j]) % MOD;
                }
            }
        }
        int result = 0;
        for (int step = 1; step <= maxMove; step++)
            result = (result + dp[step][startRow][startColumn]) % MOD;
        return result;
    }
}