一、考察频率以及难度

考察频率：⭐⭐⭐⭐⭐

笔试题难度：⭐⭐⭐

算法难度：⭐⭐⭐

一般是笔试的中等或者困难题。

二、学习技巧

掌握好常见的DP状态转移以及初始值的填写。

三、应用场景

这类题的标志非常明显，一般就是：给定一个二维的矩阵，每次只能往右或者往下走，求走到终点的最大值、最小值、方案数等。

注意，如果是可以往四个方向走，那就可能不能dp了，因为可能会导致dp的状态循环依赖。

四、算法讲解

在网格DP中，我们通常通过动态规划表（一个矩阵）来记录每个位置的状态信息，并通过递推关系来更新这些状态。常见的递推关系基于当前位置与其相邻位置的关系。

举个例子：

假设我们有一个网格图，每个格子有一个权重，我们需要找到从左上角（0,0）到右下角（n-1,m-1）的最小路径和。可以用网格DP的方法来解决这个问题。

定义状态：

dp[i][j]表示从左上角到位置(i,j)的最小路径和。

初始状态：

dp[0][0] = grid[0][0]，因为它是起点。

状态转移方程：

对于第一行（即i=0），只能从左边过来：dp[0][j] = dp[0][j-1] + grid[0][j]
对于第一列（即j=0），只能从上面过来：dp[i][0] = dp[i-1][0] + grid[i][0]
对于其他位置：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

最终结果：

dp[n-1][m-1]就是我们要找的最小路径和。

五、例题与解析

习题1 小红走迷宫

https://oj.niumacode.com/problem/P1111

小红位于一个 m x n 网格的左上角。

小红每次只能向下或者向右移动一步。机器人试图达到网格的右下角。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

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

示例 1：

输入

输出

示例 2：

输入

2 2
0 1
0 0

输出

提示：

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

题目解析

状态定义：f[i][j] 走到坐标(i,j)的方案数

状态转移：

假设该位置存在障碍物，那么f[i][j]就是0.
否则应该是可能由两个状态转移而来：f[i-1][j]+f[i][j-1]。

初始值：

对于第一行（即i=0），只能从左边过来；
对于第一列（即j=0），只能从上面过来

CPP

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> obstacleGrid(m, vector<int>(n));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> obstacleGrid[i][j];
        }
    }
    
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    
    for (int i = 1; i < n; i++) {
        dp[0][i] = obstacleGrid[0][i] == 1 ? 0 : dp[0][i - 1];
    }
    
    for (int i = 1; i < m; i++) {
        dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
        }
    }
    
    cout << dp[m - 1][n - 1] << endl;
    
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] obstacleGrid = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                obstacleGrid[i][j] = scanner.nextInt();
            }
        }
        
        int[][] dp = new int[m][n];
        dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        
        for (int i = 1; i < n; i++) {
            dp[0][i] = obstacleGrid[0][i] == 1 ? 0 : dp[0][i - 1];
        }
        
        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        System.out.println(dp[m - 1][n - 1]);
        
        scanner.close();
    }
}

Python

m,n = int(input().split())
obstacleGrid = []
for _ in range(n):
    obstacleGrid.append([int(c) for c in input().split()])

dp = [[0] * n for _ in range(m)]
dp[0][0] = 0 if obstacleGrid[0][0] == 1 else 1
for i in range(1, n):
    dp[0][i] = 0 if obstacleGrid[0][i] == 1 else dp[0][i - 1]
for i in range(1, m):
    dp[i][0] = 0 if obstacleGrid[i][0] == 1 else dp[i - 1][0]
for i in range(1, m):
    for j in range(1, n):
        dp[i][j] = 0 if obstacleGrid[i][j] == 1 else dp[i - 1][j] + dp[i][j - 1]

print(dp[m - 1][n - 1])

习题2 小红走迷宫Ⅱ

https://oj.niumacode.com/problem/P1112

小红正在探索一个神奇的迷宫，这个迷宫是由一个 n*n 的整数矩阵构成的。在这个迷宫中，每个格子都有一个数字，代表它的能量值。小红的任务是找到一条从上到下的路径，使得路径上所有格子的数字和最小，但她必须遵循以下规则：她每一步只能向下走到下一行，并且不能走到同一列的格子。

示例1

输入

输出

示例 2：

输入

1
7

输出

提示：

n grid.length grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99

题目解析

最朴素的解法其实很简单：

f[i,j]：到达位置[i,j]的最小路径和是多少
转移: MIN(f[i+1,k] + grid[i][j])，其中k不等于j。

由于需要枚举k，所以复杂度是O(n^3)，题目n是200，因此可以AC。

Python

from math import inf
n = int(input())
grid = []
for _ in range(n):
    grid.append([int(c) for c in input().split()])

f =[[inf]*n for _ in range(n)]
for j in range(n):f[-1][j] = grid[-1][j]
for i in range(n-2,-1,-1):
    for j in range(n):
        for nj in range(n):
            if nj != j:
                f[i][j] = min(f[i][j], f[i+1][nj] + grid[i][j])
print( min([f[0][j] for j in range(n)]))

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    
    vector<vector<int>> f(n, vector<int>(n, INT_MAX));
    
    for (int j = 0; j < n; j++) {
        f[n - 1][j] = grid[n - 1][j];
    }
    
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            for (int nj = 0; nj < n; nj++) {
                if (nj != j) {
                    f[i][j] = min(f[i][j], f[i + 1][nj] + grid[i][j]);
                }
            }
        }
    }
    
    int result = INT_MAX;
    for (int j = 0; j < n; j++) {
        result = min(result, f[0][j]);
    }
    
    cout << result << endl;
    
    return 0;
}

Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        
        int[][] f = new int[n][n];
        for (int[] row : f) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        for (int j = 0; j < n; j++) {
            f[n - 1][j] = grid[n - 1][j];
        }
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                for (int nj = 0; nj < n; nj++) {
                    if (nj != j) {
                        f[i][j] = Math.min(f[i][j], f[i + 1][nj] + grid[i][j]);
                    }
                }
            }
        }
        
        int result = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            result = Math.min(result, f[0][j]);
        }
        
        System.out.println(result);
        
        scanner.close();
    }
}

优化

不难发现，其实第三层循环目的是找到一个与当前纵坐标不等的最小值。因此，我们只需要维护f[i+1]的最小值和次小值即可，因为如果最小值是与当前纵坐标相等，那么就取次小值；不断更新对于每一个f[i]的最小值和次小值即可。

Python

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        f =[[inf]*n for _ in range(n)]
        MIN1, MIN2 = [inf -1], [inf, -1]  # 最大 次大
        for j in range(n):
            cur = f[-1][j] = grid[-1][j]
            if MIN1[0] > cur:
                if MIN1[0] < MIN2[0]:
                    MIN2 = MIN1
                MIN1 = [cur, j]
            elif MIN2[0] > cur:
                MIN2 = [cur, j]

        for i in range(n-2,-1,-1):
            for j in range(n):

                if j != MIN1[1]:
                    f[i][j] = min(f[i][j], MIN1[0] + grid[i][j])
                else:
                    f[i][j] = min(f[i][j], MIN2[0] + grid[i][j])

            MIN1,MIN2 = [inf,-1],[inf,-1]

            for j in range(n):
                if MIN1[0] > f[i][j]:
                    if MIN1[0] < MIN2[0]:
                        MIN2 = MIN1
                    MIN1 = [f[i][j], j]
                elif MIN2[0] > f[i][j]:
                    MIN2 = [f[i][j], j]
        return min([f[0][j] for j in range(n)])

Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }
        
        int[][] f = new int[n][n];
        for (int[] row : f) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        int[] MIN1 = {Integer.MAX_VALUE, -1}; // 最小值和其索引
        int[] MIN2 = {Integer.MAX_VALUE, -1}; // 次小值和其索引
        
        for (int j = 0; j < n; j++) {
            int cur = f[n - 1][j] = grid[n - 1][j];
            if (MIN1[0] > cur) {
                if (MIN1[0] < MIN2[0]) {
                    MIN2 = MIN1.clone();
                }
                MIN1 = new int[]{cur, j};
            } else if (MIN2[0] > cur) {
                MIN2 = new int[]{cur, j};
            }
        }
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (j != MIN1[1]) {
                    f[i][j] = Math.min(f[i][j], MIN1[0] + grid[i][j]);
                } else {
                    f[i][j] = Math.min(f[i][j], MIN2[0] + grid[i][j]);
                }
            }
            
            MIN1 = new int[]{Integer.MAX_VALUE, -1};
            MIN2 = new int[]{Integer.MAX_VALUE, -1};
            
            for (int j = 0; j < n; j++) {
                if (MIN1[0] > f[i][j]) {
                    if (MIN1[0] < MIN2[0]) {
                        MIN2 = MIN1.clone();
                    }
                    MIN1 = new int[]{f[i][j], j};
                } else if (MIN2[0] > f[i][j]) {
                    MIN2 = new int[]{f[i][j], j};
                }
            }
        }
        
        int result = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            result = Math.min(result, f[0][j]);
        }
        
        System.out.println(result);
        
        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    
    vector<vector<int>> f(n, vector<int>(n, INT_MAX));
    vector<int> MIN1 = {INT_MAX, -1}; // 最小值和其索引
    vector<int> MIN2 = {INT_MAX, -1}; // 次小值和其索引
    
    for (int j = 0; j < n; j++) {
        int cur = f[n - 1][j] = grid[n - 1][j];
        if (MIN1[0] > cur) {
            if (MIN1[0] < MIN2[0]) {
                MIN2 = MIN1;
            }
            MIN1 = {cur, j};
        } else if (MIN2[0] > cur) {
            MIN2 = {cur, j};
        }
    }
    
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            if (j != MIN1[1]) {
                f[i][j] = min(f[i][j], MIN1[0] + grid[i][j]);
            } else {
                f[i][j] = min(f[i][j], MIN2[0] + grid[i][j]);
            }
        }
        
        MIN1 = {INT_MAX, -1};
        MIN2 = {INT_MAX, -1};
        
        for (int j = 0; j < n; j++) {
            if (MIN1[0] > f[i][j]) {
                if (MIN1[0] < MIN2[0]) {
                    MIN2 = MIN1;
                }
                MIN1 = {f[i][j], j};
            } else if (MIN2[0] > f[i][j]) {
                MIN2 = {f[i][j], j};
            }
        }
    }
    
    int result = INT_MAX;
    for (int j = 0; j < n; j++) {
        result = min(result, f[0][j]);
    }
    
    cout << result << endl;
    
    return 0;
}

习题3 神奇世界游戏

https://oj.niumacode.com/problem/P1113

小红最近迷上了一款新游戏，这款游戏的场景是一个由的整数矩阵构成的神奇世界。在这个世界中，每个格子代表一个地点，格子中的数字代表该地点的高度，但是小红在移动的过程只能从低爬到高，任务是找到一条从任何一个地点出发的 最长递增路径。在这条路径上，每一步她只能向上、下、左、右四个方向移动，不能在对角线方向上移动或移动到边界外。

示例 1：

输入：

输出：

解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：

输入：

输出：

解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

输入：

1 1
1

输出：

提示：

m == matrix.length

n == matrix[i].length

1 <= m, n <= 200

0 <= matrix[i][j] <= 2^31 - 1

题目解析

这个题使用记忆化搜索来首先更为方便。

状态定义：f(i,j)表示从点i,j出发的最长递增路径的长度。

状态转移：取四个方向的最大值，max(f(i+1,j), f(i-1,j), f(i,j+1), f(i,j-1)) + 1。

PS：这个依赖关系咋一看是成循环依赖的，为什么还可以进行动态规划呢？是因为题目需要满足严格递增，所以实际上是不会成环的。

CPP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> matrix;
vector<vector<int>> mem;
int m, n;
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int dfs(int x, int y) {
    if (mem[x][y] != 0) {
        return mem[x][y];
    }

    int ans = 1;
    for (auto dir : dirs) {
        int nx = x + dir.first;
        int ny = y + dir.second;
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
            ans = max(ans, dfs(nx, ny) + 1);
        }
    }
    mem[x][y] = ans;
    return ans;
}

int solve() {
    if (matrix.empty() || matrix[0].empty()) {
        return 0;
    }

    mem.assign(m, vector<int>(n, 0));
    int ans = 1;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, dfs(i, j));
        }
    }
    
    return ans;
}

int main() {
    cin >> m >> n;
    matrix.resize(m, vector<int>(n));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    
    cout << solve() << endl;
    
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    private static int[][] matrix;
    private static int[][] mem;
    private static int m, n;
    private static int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        m = scanner.nextInt();
        n = scanner.nextInt();
        matrix = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        
        System.out.println(solve());
        
        scanner.close();
    }

    private static int solve() {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        mem = new int[m][n];
        int ans = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs(i, j));
            }
        }
        
        return ans;
    }

    private static int dfs(int x, int y) {
        if (mem[x][y] != 0) {
            return mem[x][y];
        }

        int ans = 1;
        for (int[] dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
                ans = Math.max(ans, dfs(nx, ny) + 1);
            }
        }
        mem[x][y] = ans;
        return ans;
    }
}

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        mem = [[0] * n for _ in range(m)]
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        def dfs(x, y):
            if mem[x][y] != 0:
                return mem[x][y]
            ans = 1
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:
                    ans = max(ans, dfs(nx, ny) + 1)
            mem[x][y] = ans
            return ans
        
        ans = 1
        for i in range(m):
            for j in range(n):
                ans = max(ans, dfs(i, j))
        return ans

习题4 路径条数【荣耀】

https://oj.niumacode.com/problem/P1152

一张NxM的地图上每个点的海拔高度不同；从当前点只能访问上、下、左、右四个点中还没有到达过的点，且下一步选择的点的海拔高度必须高于当前点;求从地图中的点A到点B总的路径条数除以10^9的余数。地图左上角坐标为(0,0),右下角坐标为(N-1,M-1)
输入描述

第一行输入两个整数N,M(O<N≤600，0<M≤600)用空格隔开；

接下来N行输入，每行M个整数用空格隔开，代表对应位置的海拔高度(0<海拔高度≤360000);

最后一行四个整数x,y,z,w，前两个代表A的坐标为(x,y);后两个代表B的坐标为 (z,w);

输入保证A、B坐标不同，且坐标合法
输出描述

输出一个整数并换行，整数表示从A到B总的路径条数除以10^9的余数

示例1

输入

输出

思路与代码

从x,y出发搜索即可，过程可以使用记忆化搜索进行优化，避免重复运算。每次递归有4个方向，对于四个方向的总和求总和即可。

但是注意这里的状态依赖并不会成环，因为题目要求只能往高处走，所以不可能存在走回来的情况。

CPP

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 605;
const int MOD = 1000000007;

int n, m;
vector<vector<int>> matrix;
int dp[MAX_N][MAX_N];

// Directions: right, down, left, up
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int dfs(int i, int j) {
    if (i == n - 1 && j == m - 1) {
        return 1;
    }
    
    if (dp[i][j] != -1) {
        return dp[i][j];
    }
    
    int count = 0;
    for (auto dir : dirs) {
        int ni = i + dir.first;
        int nj = j + dir.second;
        if (ni >= 0 && ni < n && nj >= 0 && nj < m && matrix[ni][nj] > matrix[i][j]) {
            count += dfs(ni, nj);
            count %= MOD;
        }
    }
    
    dp[i][j] = count;
    return count;
}

int main() {
    cin >> n >> m;
    matrix.resize(n, vector<int>(m));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }
    
    // Initialize dp array with -1 (indicating not computed)
    memset(dp, -1, sizeof(dp));
    
    int startX, startY, endX, endY;
    cin >> startX >> startY >> endX >> endY;
    
    --startX; --startY; --endX; --endY;  // convert to 0-based index
    
    int result = dfs(startX, startY);
    cout << result << endl;
    
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int MAX_N = 605;
    static final int MOD = 1000000007;
    static int n, m;
    static int[][] matrix;
    static int[][] dp;

    // Directions: right, down, left, up
    static int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static int dfs(int i, int j) {
        if (i == n - 1 && j == m - 1) {
            return 1;
        }
        
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        
        int count = 0;
        for (int[] dir : dirs) {
            int ni = i + dir[0];
            int nj = j + dir[1];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && matrix[ni][nj] > matrix[i][j]) {
                count += dfs(ni, nj);
                count %= MOD;
            }
        }
        
        dp[i][j] = count;
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        matrix = new int[n][m];
        dp = new int[MAX_N][MAX_N];
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        
        // Initialize dp array with -1 (indicating not computed)
        for (int i = 0; i < MAX_N; ++i) {
            Arrays.fill(dp[i], -1);
        }
        
        int startX = scanner.nextInt() - 1;
        int startY = scanner.nextInt() - 1;
        int endX = scanner.nextInt() - 1;
        int endY = scanner.nextInt() - 1;
        
        int result = dfs(startX, startY);
        System.out.println(result);
        
        scanner.close();
    }
}

Python

n,m = map(int, input().split(" "))
matrix = []
for i in range(n):
    matrix.append([int(c) for c in input().split(" ")])

x,y,z,w = map(int, input().split(" "))
dirs = [[0,1],[1,0],[0,-1],[-1,0]]

dp = {}
def dfs(i,j):
    if i == z and j == w: return 1
    if (i,j) in dp: return dp[(i,j)]
    cur = 0
    for dir in dirs:
        ni, nj = i + dir[0], j + dir[1]
        if ni < 0 or nj < 0 or ni >= n or nj >= m or matrix[i][j] >= matrix[ni][nj]: continue
        cur += dfs(ni, nj)
    dp[(i,j)] = cur
    return cur

print(dfs(x,y))

六、常见陷阱

初始值容易填错，特别需要注意第一行和第一列。
需要注意是否存在依赖成环的问题，如果存在的话，可能要考虑其他算法，而不是一味dp。

目录CONTENT

二维图DP

一、考察频率以及难度

二、学习技巧

三、应用场景

四、算法讲解

五、例题与解析

习题1 小红走迷宫

习题2 小红走迷宫Ⅱ

习题3 神奇世界游戏

习题4 路径条数【荣耀】

六、常见陷阱

二维图DP

一、考察频率以及难度

二、学习技巧

三、应用场景

四、算法讲解

五、例题与解析

习题1 小红走迷宫

习题2 小红走迷宫Ⅱ

习题3 神奇世界游戏

习题4 路径条数 【荣耀】

六、常见陷阱

习题4 路径条数【荣耀】