题意整理。

• 给定一个n行m列的矩阵，矩阵的每个格子里有一个字母，每个字母对应一个分数。
• 求小红从左上角出发，到右下角为止，最多能获得多少分。

方法一（二维dp）

1.解题思路

• 首先定义一个二维dp数组，dp[i][j]表示走到i行j列的时候，小红最多能获取多少分。
• 然后确定状态如何转化。每一步中，小红要么从左边格子到当前位置，要么从上边格子到当前位置，两者取较大的一个，所以$dp[i][j]=Math\mathrm{.}max(dp[i-1][j],dp[i][j-1])+getScore(arr[i][j])dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+getScore(arr[i][j])$。

图解展示：

2.代码实现

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        //定义矩阵，用于存放对应的字母
        char[][] arr=new char[n+1][m+1];
        for(int i=1;i<=n;i++){
            String s=sc.next();
            for(int j=1;j<=m;j++){
                arr[i][j]=s.charAt(j-1);
            }
            
        }

        //dp[i][j]表示走到i行j列的时候，最多能获取多少分
        int[][] dp=new int[n+1][m+1];
        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(arr[i][j]);
            }
        }
        
        System.out.println(dp[n][m]);
        
    }
    
    //判断选择某个字母可以获得几分
    private static int getScore(char c){
        if(c=='l') return 4;
        if(c=='o') return 3;
        if(c=='v') return 2;
        if(c=='e') return 1;
        return 0;
    }
}

3.复杂度分析

• 时间复杂度：两层循环，最多执行$n\ast mn*m$次，所以时间复杂度为$O(n\ast m)O(n*m)$。
• 空间复杂度：需要额外大小为$(n+1)\ast (m+1)(n+1)*(m+1)$的dp数组，所以空间复杂度为$O(n\ast m)O(n*m)$。