二维dp

要做一些题巩固知识

package com.zhang.reflection.面试.算法模版.动态规划;
import java.util.Scanner;
/**
 * 有一个 n*mn∗m 的矩形方阵，每个格子上面写了一个小写字母。
 * 小红站在矩形的左上角，她每次可以向右或者向下走，走到某个格子上就可以收集这个格子的字母。
 * 小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分，拿到一个 o 字母可以得 3 分，拿到一个 v 字母可以得 2 分，拿到一个 e 字母可以得 1 分。
 * 她想知道，在最优的选择一条路径的情况下，她最多能获取多少分？
 *
 * 3 2
 * ab
 * cd
 * ef
 *
 * 1
 */
public class 二维dp {
    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;
    }
}