字母收集

难度：2星

经典的二维dp题目。设从起点到当前点的最大收益为 $dp[i][j]dp[i][j]$，那么显然当前点 $(i,j)(i,j)$ 要么从 $(i-1,j)(i-1,j)$ 过来，要么从 $(i,j-1)(i,j-1)$ 过来。因此有dp方程：

$dp[i][j]=max(dp[i-1][j],dp[i][j-1])+val[i][j]dp[i][j]=max(dp[i-1][j],dp[i][j-1])+val[i][j]$

其中 $val[i][j]val[i][j]$ 代表当前字母的权值。

#include<bits/stdc++.h>
using namespace std;
int dp[555][555];
string a[555];
int f(char c){
    if(c=='l')return 4;
    if(c=='o')return 3;
    if(c=='v')return 2;
    if(c=='e')return 1;
    return 0;
}
int main(){
    int n,m,i,j;
    cin>>n>>m;
    for(i=0;i<=n;i++)cin>>a[i];
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            int temp=0;
            if(i>0)temp=max(temp,dp[i-1][j]);
            if(j>0)temp=max(temp,dp[i][j-1]);
            dp[i][j]=temp+f(a[i][j]);
        }
    }
    cout<<dp[n-1][m-1];
}