#yyds干货盘点# 动态规划专题：字母收集

1.简述：

有一个  的矩形方阵，每个格子上面写了一个小写字母。小红站在矩形的左上角，她每次可以向右或者向下走，走到某个格子上就可以收集这个格子的字母。小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分，拿到一个 o 字母可以得 3 分，拿到一个 v 字母可以得 2 分，拿到一个 e 字母可以得 1 分。她想知道，在最优的选择一条路径的情况下，她最多能获取多少分？

输入描述：

接下来的  行 每行一个长度为  的、仅有小写字母构成的字符串，代表矩形方阵。

输出描述：

小红最大可能的得分。

示例1

输入：

3 2
ab
cd
ef

输出：

1

说明：

选择下、下、右）这条路径即可，可以收集到 acef 这四个字母各一次，获得 0+0+1+0=1 分。

示例2

输入：

2 3
lle
ove

输出：

11

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;
    }
}