描述

给一个$n\ast mn*m$的字母矩阵，每个字母对应一个价值，问从左上角出发所能达到的最大价值

思路

• 二维DP，令$dp[i][j]dp[i][j]$表示从左上角到达$(i,j)(i,j)$所能得到的最大价值，则答案为$dp[n][m]dp[n][m]$，初始化时，所有$dp[i][j]dp[i][j]$的值为当前点的价值，转移方程为$dp[i][j]=\max (dp[i-1][j]+dp[i][j],dp[i][j-1]+dp[i][j])dp[i][j]=\backslash max(dp[i-1][j]+dp[i][j],dp[i][j-1]+dp[i][j])$

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
char s[MAXN][MAXN];
int dp[MAXN][MAXN];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='l') dp[i][j]=4;
            if(s[i][j]=='o') dp[i][j]=3;
            if(s[i][j]=='v') dp[i][j]=2;
            if(s[i][j]=='e') dp[i][j]=1;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dp[i][j]=max(dp[i-1][j]+dp[i][j],dp[i][j-1]+dp[i][j]);
    printf("%d",dp[n][m]);
}

时间复杂度$O(nm)O(nm)$，空间复杂度$O(nm)O(nm)$