题解 | 字母收集

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine(); 

        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine().trim();
            grid[i] = line.toCharArray();
        }

        int[][] scores = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c = grid[i][j];
                switch (c) {
                    case 'l':
                        scores[i][j] = 4;
                        break;
                    case 'o':
                        scores[i][j] = 3;
                        break;
                    case 'v':
                        scores[i][j] = 2;
                        break;
                    case 'e':
                        scores[i][j] = 1;
                        break;
                    default:
                        scores[i][j] = 0;
                        break;
                }
            }
        }

        int[][] dp = new int[n][m];
        dp[0][0] = scores[0][0];

        for (int j = 1; j < m; j++) {
            dp[0][j] = dp[0][j - 1] + scores[0][j];
        }

        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + scores[i][0];
        }

        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]) + scores[i][j];
            }
        }

        System.out.println(dp[n - 1][m - 1]);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取矩阵的行列数和每个格子的字符。
2. 得分预处理：将每个字符转换为对应的得分，存储在一个二维数组中。
3. 动态规划数组初始化：处理左上角、第一行和第一列的得分。
4. 动态规划填充：根据状态转移方程填充其余位置的得分。
5. 结果输出：输出右下角的最大得分。