题解 | #字母收集#

本题可利用动态规划进行求解，数据是 n * m 的矩阵，利用二维 dp，每次移动只能向右或向下，初始值 dp[0][0] = v00， 第一行 dp[i][j] = dp[i - 1][j] + vij, 第一列 dp[i][j] = dp[i][j - 1] + vij, 当 i > 0 且 j > 0 时 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + vij，进行状态转移；代码如下:

n, m = map(int, input().strip().split())
data = [list(input().strip()) for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
count = {"l":4, "o":3, "v": 2, "e": 1}
for i in range(n):
    for j in range(m):
        if i == j == 0:
            dp[i][j] = count[data[i][j]] if data[i][j] in count else 0
        elif i > 0 and j == 0:
            dp[i][j] = dp[i - 1][j] + (count[data[i][j]] if data[i][j] in count else 0)
        elif i == 0 and j > 0:
            dp[i][j] = dp[i][j - 1] + (count[data[i][j]] if data[i][j] in count else 0)
        elif i > 0 and j > 0:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + (count[data[i][j]] if data[i][j] in count else 0)
print(dp[-1][-1])