代码探险家

这个屌丝很懒，什么也没留下！

热门标签

动态规划路径_动态路径规划

作者：代码探险家 | 2024-07-26 02:01:34

踩

动态路径规划

动态规划

https://leetcode-cn.com/problems/out-of-boundary-paths/solution/dong-tai-gui-hua-suo-you-lu-jing-wen-ti-94bal/

一、动态规划的标志

1、无后效性（无反扑）

后面的状态由前面的状态决定，也就是说前面的状态的改变会影响到后面，但是后面不会反过来影响前面。

2、通过数据范围猜测

DP 是一个 递推的过程，如果数据范围是 10⁵~10⁶ 的话，考虑使用一维 DP 来解决；如果数据范围是 10²~10³ 的话，考虑使用二维 DP 来做 …

二、状态定义

相当一部分题目的状态定义是与「结尾」和「答案」有所关联的。

三、状态转移方程

四、对状态转移的要求

状态转移是「不漏」还是「不重不漏」取决于问题本身：

如果是求最值的话，只需要确保 「不漏」 即可，因为重复不影响结果。
如果是求 方案数 的话，需要确保 「不重不漏」。

五、动态规划的时间复杂度

有多少个状态，复杂度/计算量就是多少。
因此一维 DP 的复杂度通常是线性的，而二维 DP 的复杂度通常是平方的。

六、分类

线性、区间、树形、插头、斜率 …

62. 不同路径

定义 $f [i] [j]$ 为到达位置 (i, j) 的不同路径数量。
初始化 $f [0] [0] = 1$
状态转移方程 $f [i] [j] = f [i] [j - 1] + f [i - 1] [j]$
最终的答案 $f [n - 1] [m - 1]$

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        f[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) f[i][j] = f[i - 1][j] + f[i][j - 1];
                else if (i > 0) f[i][j] = f[i - 1][j];
                else if (j > 0) f[i][j] = f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

也可以先初始化第一行和第一列，其它从 1 开始不用判断条件，直接用转移方程。

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 第一行
        for (int i = 1; i < m; i++) {           
            for (int j = 1; j < n; j++) { // 第一列全为 1
                dp[j] +=  dp[j - 1];                
            }
        }
        return dp[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

63. 不同路径 II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = 1 - obstacleGrid[0][0]; // 是否是障碍物
        for (int i = 0; i < m; i++) {
            // 先处理第一个，由上一个决定
            dp[0] = (1 - obstacleGrid[i][0]) * dp[0]; 
            for (int j = 1; j < n; j++) {
                // 转移方程 上一个 + 前一个
                dp[j] = (1 - obstacleGrid[i][j]) * (dp[j - 1] + dp[j]);
            }
        }
        return dp[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

64. 最小路径和

定义 $f [i] [j] 为从 (0, 0)$ 开始到达位置 (i, j) 的最小总和。
初始化 $f [0] [0] = g r i d [0] [0]$
转移方程 $f [i] [j] = min (f [i] [j - 1], f [i - 1] [j]) + g r i d [i] [j]$
最终的答案 $f [m - 1] [n - 1]$

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] f = new int[m][n];
        // 第一行 前缀和
        f[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            f[0][i] = f[0][i - 1] + grid[0][i];
        }
        // 第一列
        for (int i = 1; i < m; i++) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int minPathSum(int[][] grid) {    	
        int m = grid.length, n = grid[0].length;
        int[] f = new int[n];
        // 第一行 前缀和
        f[0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] + grid[0][i];
        } 
        
        for (int i = 1; i < m; i++) {
            f[0] += grid[i][0]; // 第一列
            for (int j = 1; j < n; j++) {           
                f[j] = Math.min(f[j], f[j - 1]) + grid[i][j];
            }
        }
        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

120. 三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] f = new int[n];
        // 三角形最后一行为初值
        for (int i = 0; i < n; i++) {
            f[i] = triangle.get(n - 1).get(i);
        }
        // 倒数第二行开始，逆序遍历
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[j] = Math.min(f[j], f[j + 1]) + triangle.get(i).get(j);
            }
        }

        return f[0];
    }
}
        
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size(), inf = Integer.MAX_VALUE;
        int[] f = new int[n];
        Arrays.fill(f, inf);
        f[0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                f[j] = Math.min(f[j - 1], f[j]) + triangle.get(i).get(j);
            }
            // 后更新
            f[0] += triangle.get(i).get(0);
        }
        int res = inf;
        for (int x : f) res = Math.min(res, x);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

1575. 统计所有可行路径

2 <= locations.length <= 100 ，会想到 DFS，DFS 通常是指数级别的复杂度，数据范围不出超过 30，「记忆化搜索」可以。

「DFS 的三部曲」

递归函数的「入参」和「出参」
递归函数的出口（Base Case）
「最小单元」处理逻辑

缓存器的设计二维数组 cache[][]

cache[pos][rest ] 代表从位置 pos 出发，当前剩余的油量为 rest 的前提下，到达目标位置的「路径数量」。

class Solution {
    static final int MOD = 1000000007;
    int[][] f;
    int[] locs;
    int end;
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        f = new int[locations.length][fuel + 1];
        this.locs = locations;
        this.end = finish;
        return dfs(start, fuel);
    }

    public int dfs(int pos, int rest) {
        if (f[pos][rest] != 0) return f[pos][rest];        
        if (Math.abs(locs[pos] - locs[end]) > rest) return 0; 
        
        for (int i = 0; i < locs.length; ++i) {
            if (pos == i) continue;
            int cost = Math.abs(locs[pos] - locs[i]);
            if (cost <= rest) {
                f[pos][rest] += dfs(i, rest - cost);
                f[pos][rest] %= MOD;
            }     
        }
        if (pos == end) {
            f[pos][rest]++;
            f[pos][rest] %= MOD;
        }
        return f[pos][rest];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    int mod = 1000000007;
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        // f[i][j] 代表从位置 i 出发，当前油量为 j 时，到达目的地的路径数
        int[][] f = new int[n][fuel + 1];
        
        // 对于本身位置就在目的地的状态，路径数为 1
        for (int i = 0; i <= fuel; i++) f[finish][i] = 1;
        // 从态转移方程 f[i][fuel] += f[k][fuel-need]
        // 在计算 f[i][fuel] 的时候依赖于 f[k][fuel - need]
        // 其中 i 和 k 并无严格的大小关系
        // 而 fuel 和 fuel-need 具有严格大小关系：fuel >= fuel - need
        // 因此需要先从小到大枚举油量
        for (int cur = 0; cur <= fuel; cur++) {
            for (int i = 0; i < n; i++) {
                for (int k = 0; k < n; k++) {
                    if (i != k) {
                        int need = Math.abs(locations[i] - locations[k]);
                        if (cur >= need) {
                            f[i][cur] += f[k][cur-need];
                            f[i][cur] %= mod;
                        }
                    }
                }
            }
        }
        return f[start][fuel];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    static final int MOD = 1000000007;
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int n = locations.length;
        int startPos = locations[start];
        int finishPos = locations[finish];
        Arrays.sort(locations);
        // for (int i = 0; i < n; ++i) {
        //     if (startPos == locations[i]) start = i;
        //     if (finishPos == locations[i]) finish = i;
        // }
        start = Arrays.binarySearch(locations, startPos);
        finish = Arrays.binarySearch(locations, finishPos);

        int[][] dpL = new int[n][fuel + 1];
        int[][] dpR = new int[n][fuel + 1];
        dpL[start][0] = dpR[start][0] = 1;
        
        for (int i = 0; i <= fuel; ++i) {
            for (int city = n - 2; city >= 0; --city) {
                int delta = locations[city + 1] - locations[city];
                if (i >= delta) {
                    dpL[city][i] = ((i == delta ? 0 : dpL[city + 1][i - delta]) * 2 % MOD + dpR[city + 1][i - delta]) % MOD;
                }
            }
            for (int city = 1; city < n; ++city) {
                int delta = locations[city] - locations[city - 1];
                if (i >= delta) {
                    dpR[city][i] = ((i == delta ? 0 : dpR[city - 1][i - delta]) * 2 % MOD + dpL[city - 1][i - delta]) % MOD;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i <= fuel; ++i) {
            ans += (dpL[finish][i] + dpR[finish][i]) % MOD;
            ans %= MOD;
        }
        if (start == finish) ans--;
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

576. 出界的路径数

class Solution {
    int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int MOD = 1000000007;
    int[][][] memo;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memo = new int[m][n][maxMove + 1];
        return dfs(m, n, maxMove, startRow, startColumn);
    }

    private int dfs(int m, int n, int moveCount, int i, int j) {
        // 越界了就找到了一条路径
        if (i < 0 || j < 0 || i >= m || j >= n) return 1;
        // 没有移动次数了，返回0
        if (moveCount == 0) return 0;

        // 缓存中存在
        if (memo[i][j][moveCount] != 0) return memo[i][j][moveCount];

        // 剪枝：如果小球不管怎么移动都无法越出网格，那就剪掉这个枝
        if (i >= moveCount && j >= moveCount && i + moveCount < m && j + moveCount < n) return 0;

        // 从这个点出发的符合条件的路径数量
        int res = 0;
        for (int[] dir : dirs) {
            // 记得取余
            res = (res + dfs(m, n, moveCount - 1, i + dir[0], j + dir[1])) % MOD;
        }

        // 记录缓存
        memo[i][j][moveCount] = res;
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

dp[i][j][k] 表示从 [i, j] 位置出发，移动步数不超过 j 的路径数量。
$d p [i] [j] [k] = d p [i - 1] [j] [k - 1] + d p [i + 1] [j] [k - 1] + d p [i] [j - 1] [k - 1] + d p [i] [j + 1] [k - 1]$

class Solution {
    int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int MOD = 1000000007;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int[][][] dp = new int[m][n][maxMove + 1];
        // 移动步数 2 的都是从移动步数 1 的转移来的
        // 移动步数 3 的都是从移动步数 2 的转移来的
        // 所以，要从移动步数从 1 开始递增
        for (int k = 1; k <= maxMove; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 处理四条边，注意不能合并
                    if (i == 0) dp[i][j][k]++;
                    if (j == 0) dp[i][j][k]++;
                    if (i == m - 1) dp[i][j][k]++;
                    if (j == n - 1) dp[i][j][k]++;

                    // 中间的位置，向四个方向延伸
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            dp[i][j][k] = (dp[i][j][k] + dp[x][y][k - 1]) % MOD;
                        }
                    }
                }
            }
        }
        return dp[startRow][startColumn][maxMove];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

一维数组

class Solution {
    int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int MOD = 1000000007;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int[] dp = new int[m * n];        
        for (int k = 1; k <= maxMove; k++) {
            // 滚动数组
            int[] tmp = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int index = index(i, j, n);
                    // 处理四条边
                    if (i == 0) tmp[index]++;
                    if (j == 0) tmp[index]++;
                    if (i == m - 1) tmp[index]++;
                    if (j == n - 1) tmp[index]++;

                    // 中间的位置，向四个方向延伸
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        int nextIndex = index(x, y, n);
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            tmp[index] = (tmp[index] + dp[nextIndex]) % MOD;
                        }
                    }
                }
            }
            dp = tmp;
        }
        return dp[index(startRow, startColumn, n)];
    }

    private int index(int i, int j, int n) {
        return i * n + j;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int findPaths(int m, int n, int N, int i, int j) {
        // dp[i][j][k]:表示从(i, j)出发第 k 步出界的路径总数，等价于从外界出发第k步走到(i, j)的路径总数
        long[][][] dp = new long[m + 2][n + 2][N + 1];
        int mod = 1000000007;
        if (N == 0) return 0;
        for (int r = 0; r <= m + 1; r++) {
            // 第 0 列和第 n + 1 列
            dp[r][0][0] = 1;
            dp[r][n + 1][0] = 1;
        }
        for (int c = 0; c <= n + 1; c++) {
            // 第 0 行和 第 m + 1 行
            dp[0][c][0] = 1;
            dp[m + 1][c][0] = 1;
        }

        for (int k = 1; k <= N; k++) {
            for (int r = 1; r <= m; r++) {
                for (int c = 1; c <= n; c++) {
                    dp[r][c][k] = (dp[r - 1][c][k - 1] + dp[r + 1][c][k - 1] + dp[r][c - 1][k - 1] + dp[r][c + 1][k - 1]) % mod;
                }
            }
        }
        long ans = 0;
        // 的结果加起来
        for (int k = 1; k <= N; k++) {
            ans = (ans + dp[i + 1][j + 1][k]) % mod;
        }
        return (int)ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/883007

动态规划 路径_动态路径规划