LeetCode周赛高频题解析：用动态规划速解字母收集问题

在算法竞赛的紧张氛围中，遇到二维网格路径优化问题时，动态规划(DP)往往是最高效的解决方案。这类问题在LeetCode周赛和各大厂笔试中频繁出现，比如我们今天要讨论的"字母收集"问题——它本质上是一个变种的"最大路径和"问题。

1. 问题分析与抽象化建模

字母收集问题的核心在于：在一个n*m的字母矩阵中，从左上角出发，每次只能向右或向下移动，收集经过的字母，其中'l'、'o'、'v'、'e'分别对应4、3、2、1分，其他字母0分，求到达右下角时的最大得分。

关键识别点 ：

• 移动限制（右/下）暗示了DP的可行性
• 每个格子的得分只与字母类型相关
• 需要累计路径上的最大得分

这类网格DP问题通常具有以下特征：

1. 状态定义明确： dp[i][j] 表示到达(i,j)时的最优解
2. 转移方程清晰：基于移动限制（通常来自上方或左方）
3. 边界条件固定：首行/首列通常只能从一个方向到达

2. 动态规划模板解析

对于网格DP问题，我们可以套用一个通用模板：

// 初始化DP表
int[][] dp = new int[n][m];

// 边界条件处理
dp[0][0] = valueAtStart;
for (int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + value[i][0];
for (int j = 1; j < m; j++) dp[0][j] = dp[0][j-1] + value[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]) + value[i][j];
    }
}

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

针对字母收集问题，我们需要做以下适配：

1. 将字母转换为对应分值
2. 处理1-based索引（如果输入从(1,1)开始）
3. 考虑大矩阵情况下的空间优化

3. 竞赛级Java实现

以下是经过优化的完整实现，考虑了竞赛中的常见输入格式和效率要求：

import java.util.*;

public class LetterCollection {
    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();
        }
        
        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]);
        }
        
        // 填充DP表
        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. 使用switch语句处理字母评分，比if-else更清晰
2. 分离分数计算逻辑，提高代码可读性
3. 显式处理边界条件，避免在双重循环中判断

4. 空间复杂度优化技巧

当处理大矩阵时（如500x500），我们可以进一步优化空间使用：

public static int maxScoreOptimized(char[][] grid) {
    int m = grid[0].length;
    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 < grid.length; 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]);
        }
    }
    
    return dp[m-1];
}

这种优化将空间复杂度从O(n*m)降到O(m)，在处理大矩阵时能有效减少内存使用。

5. 常见变种与应对策略

在竞赛中，这类问题常有多种变体，我们需要快速识别并调整解决方案：

变种类型	关键特征	解法调整
最小路径和	求最小值而非最大值	将Math.max改为Math.min
障碍物网格	某些格子不可通过	在DP转移时跳过障碍物格子
多路径收集	可以重复经过某些格子	可能需要三维DP或记忆化搜索
多目标字母	需要收集特定字母组合	增加DP状态维度记录收集情况

例如，如果题目改为"必须收集至少一个'l'和一个'o'"，我们就需要将状态扩展为 dp[i][j][k] ，其中k用位掩码表示已收集的字母情况。

6. 竞赛实战技巧

在时间紧迫的编程竞赛中，以下几点可以帮助你更快解决此类问题：

1. 快速识别模式 ：看到网格+路径优化，立即想到DP
2. 模板化编码 ：准备好网格DP的代码模板
3. 边界处理 ：先处理第一行和第一列，再填充内部
4. 空间优化 ：根据问题规模决定是否使用滚动数组
5. 调试技巧 ：对于小样例，手动计算几个关键点的DP值验证

提示：在比赛中，建议先写出基础DP解法，确保正确性后再考虑优化。过早优化可能引入错误并浪费时间。

7. 复杂度分析与适用场景

让我们分析不同解法的性能特点：

基础DP解法 ：

• 时间复杂度：O(n*m) —— 必须遍历整个网格
• 空间复杂度：O(n*m) —— 完整的DP表

优化空间解法 ：

• 时间复杂度：O(n*m) —— 相同
• 空间复杂度：O(m) —— 仅保留一行

对于LeetCode等编程竞赛中的约束条件：

• 当n,m ≤ 200时，基础解法完全足够
• 当n,m ≤ 1000时，建议使用空间优化版本
• 对于更大的网格，可能需要考虑并行算法或其他优化

在实际笔试中，这类问题通常出现在中等难度环节，建议分配10-15分钟完成，包括问题分析、编码和测试。