题解 | #字母收集#

使用一个辅助数组sum记录从起点走到当前位置的最大值，即sum.at(i).at(j)表示从(0,0)走到(i,j)的所有路径中的最大值。最后返回sum.at(n-1).at(m-1)即为走完整个矩阵的最大值。

由于遍历了存储矩阵的二维数组，时间复杂度为O(nm)。由于使用了sum辅助数组，空间复杂度为O(nm)。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<char> stemp(m);
    vector<vector<char>> arr(n, stemp);
    vector<int> itemp(m, 0);
    vector<vector<int>> sum(n, itemp);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> arr.at(i).at(j);
            if(arr.at(i).at(j) == 'l'){
                sum.at(i).at(j) = 4;
            }
            else if(arr.at(i).at(j) == 'o'){
                sum.at(i).at(j) = 3;
            }
            else if(arr.at(i).at(j) == 'v'){
                sum.at(i).at(j) = 2;
            }
            else if(arr.at(i).at(j) == 'e'){
                sum.at(i).at(j) = 1;
            }
            if(i == 0 && j != 0){
                sum.at(i).at(j) += sum.at(i).at(j - 1);
            }
            else if(i != 0 && j == 0){
                sum.at(i).at(j) += sum.at(i - 1).at(j);
            }
            else if(i != 0 && j != 0){
                sum.at(i).at(j) += max(sum.at(i).at(j - 1), sum.at(i - 1).at(j));
            }
        }
    }
    cout << sum.at(n - 1).at(m - 1);
    return 0;
}