牛客对应链接：字母收集_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
基础路径问题的 dp 模型。
- 状态表示：dp[i][j]：到达 i, j 位置的时候，最多的分数是多少。（返回 dp[n][m]）
- 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + t
- 遍历顺序：从上往下，从左往右。
注意：小心边界情况和数组类型的设定（这里的 g 里面是字符，要用 char，dp 里面存的是整型，要用 int）。
二、代码
#include <iostream> using namespace std; const int N = 510; char g[N][N]; int dp[N][N]; int n, m; int main() { cin >> m >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> g[i][j]; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { int t = 0; if(g[i][j] == 'l') t = 4; else if(g[i][j] == 'o') t = 3; else if(g[i][j] == 'v') t = 2; else if(g[i][j] == 'e') t = 1; dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + t; } } cout << dp[n][m] << endl; return 0; }
三、反思与改进
最近一做到矩阵的题目就想到 dfs，好在后面反应过来这题就是很普通的 dp 路径问题，不过卡在了初始化那一块，刚开始想着先把第一行和第一列进行初始化，后面想想不对，除了 dp[0][0] 可以确定，其它的都不一定是其本身的值。于是，只对下标 dp[0][0] 进行了初始化，但却忽略了后面递推关系会用到第一行和第一列的值。其实只需要把 i=0 和 j=0 空出来，从 i=1 和 j=1 开始，一直到 n 和 m 结束，去读入数据和遍历数组，即可解决这个问题。
