LeetCode周赛高频题型解析：二维网格动态规划实战指南

参加算法竞赛时，二维网格动态规划问题总是让不少选手感到棘手。这类题目看似简单，但在紧张的比赛环境中，边界条件处理不当、状态转移方程写错、初始化遗漏等问题频频出现。本文将以经典的"字母收集"问题为例，深入剖析这类题型的解题思路，提供可直接套用的Java代码模板，并分享竞赛中的实用调试技巧。

1. 动态规划问题快速识别

在LeetCode周赛或笔试中，遇到二维网格类题目时，如何快速判断是否适用动态规划解法？以下是几个关键特征：

• 网格移动限制 ：题目通常限定移动方向（如只能向右或向下）
• 最优解需求 ：要求计算最大/最小路径值、最多/最少收集物品等
• 子问题重叠 ：当前格子的最优解依赖于相邻格子的解

以"字母收集"为例，小红只能向右或向下移动，需要计算最大得分，完全符合上述特征。遇到这类题目，动态规划应该是首选解法。

常见变种题型 ：

1. 不同移动方向限制（如增加对角线移动）
2. 障碍物处理（某些格子不可达）
3. 多维度状态（如同时考虑收集物品和步数限制）
4. 路径回溯需求（不仅求值还要输出具体路径）

2. Java动态规划模板详解

下面提供一个经过竞赛验证的通用Java模板，适用于大多数二维网格DP问题：

import java.util.Scanner;

public class GridDP {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        char[][] grid = new char[n][m];
        
        // 读取网格数据
        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
        }
        
        // DP表初始化
        int[][] dp = new int[n][m];
        
        // 边界条件处理
        dp[0][0] = getScore(grid[0][0]);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + getScore(grid[i][0]);
        }
        for (int j = 1; j < m; j++) {
            dp[0][j] = dp[0][j-1] + getScore(grid[0][j]);
        }
        
        // 状态转移
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + getScore(grid[i][j]);
            }
        }
        
        System.out.println(dp[n-1][m-1]);
    }
    
    private static int getScore(char c) {
        switch(c) {
            case 'l': return 4;
            case 'o': return 3;
            case 'v': return 2;
            case 'e': return 1;
            default: return 0;
        }
    }
}

关键点解析 ：

1. 边界处理 ：第一行和第一列需要单独初始化，因为它们只能从一个方向到达
2. 状态转移 ：核心是 Math.max(dp[i-1][j], dp[i][j-1]) ，表示选择得分更高的路径
3. 得分计算 ：抽离为独立方法，提高代码可读性和可维护性

3. 竞赛中的常见陷阱与调试技巧

即使掌握了算法思路，实际比赛中仍可能遇到各种意外情况。以下是几个高频错误点及应对策略：

3.1 数组越界问题

典型表现 ：

• 访问 dp[-1][j] 或 dp[i][-1]
• 网格行列数混淆（特别是从1开始索引时）

调试技巧 ：

// 在状态转移前添加边界检查
if (i > 0 && j > 0) {
    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + score;
} else if (i > 0) {
    dp[i][j] = dp[i-1][j] + score;
} else if (j > 0) {
    dp[i][j] = dp[i][j-1] + score;
}

3.2 初始化遗漏

常见错误 ：

• 忘记初始化起点 dp[0][0]
• 第一行/列的初始化逻辑错误

正确做法 ：

// 起点必须显式初始化
dp[0][0] = getScore(grid[0][0]);

// 第一列只能从上向下走
for (int i = 1; i < n; i++) {
    dp[i][0] = dp[i-1][0] + getScore(grid[i][0]);
}

// 第一行只能从左向右走
for (int j = 1; j < m; j++) {
    dp[0][j] = dp[0][j-1] + getScore(grid[0][j]);
}

3.3 空间复杂度优化

当网格较大时（如500x500），可以考虑空间优化：

// 使用滚动数组优化空间
int[] dp = new int[m];
dp[0] = getScore(grid[0][0]);

// 初始化第一行
for (int j = 1; j < m; j++) {
    dp[j] = dp[j-1] + getScore(grid[0][j]);
}

for (int i = 1; i < n; i++) {
    // 每行第一个元素特殊处理
    dp[0] += getScore(grid[i][0]);
    
    for (int j = 1; j < m; j++) {
        dp[j] = Math.max(dp[j], dp[j-1]) + getScore(grid[i][j]);
    }
}

4. 复杂度分析与进阶优化

理解算法复杂度对于竞赛中的策略选择至关重要。

基本分析 ：

• 时间复杂度：O(nm) — 必须遍历整个网格
• 空间复杂度：O(nm) — 基础二维DP表

优化方向 ：

1. 滚动数组 ：空间降至O(min(n,m))
2. 输入优化 ：使用BufferedReader代替Scanner加速输入
3. 并行计算 ：对于超大网格，考虑分块并行处理

输入输出优化示例 ：

import java.io.*;

public class FastIOExample {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]), m = Integer.parseInt(nm[1]);
        
        char[][] grid = new char[n][];
        for (int i = 0; i < n; i++) {
            grid[i] = br.readLine().toCharArray();
        }
        
        // ... DP计算逻辑 ...
        
        System.out.println(dp[n-1][m-1]);
    }
}

在实际比赛中，建议先写出正确的基础解法，确保得分后再考虑优化。过早优化可能导致难以调试的错误，反而浪费时间。