题目链接: DP39 字母收集
用动态规划求解, 先定义状态表示:
dp[i][j]: 表示在坐标 (i,j) 处可获得的最大得分
根据题意, 只能向下和向右走, 那么可以得出走到坐标 (i, j) 位置无非从左边来或者从上边来, 根据状态表示, 也就是取左边和上边来的最大值加上 (i, j) 位置本身的值即为 dp[i][j], 那么状态转移方程为:
dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + 坐标(i, j)的字母的得分
图示:
定义数组时多开一行和一列, 这样方便, 不用处理边界问题, 不用特别初始化, 默认的 0 即可.
题解代码:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<char>> arr(n + 1, vector<char>(m + 1));
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cin >> arr[i][j];
int score = 0;
switch(arr[i][j])
{
case 'l':
score = 4;
break;
case 'o':
score = 3;
break;
case 'v':
score = 2;
break;
case 'e':
score = 1;
break;
}
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + score;
}
}
cout << dp[n][m] << endl;
return 0;
}