递归 + 记忆化
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int memo[101][101];
int dfs(int x, int y, vector<vector<int>> &vec) {
if (x == (int)vec.size() - 1 && y == (int)vec[0].size() - 1) {
return vec[x][y];
}
if (memo[x][y] != -1) {
return memo[x][y];
}
if (x == (int)vec.size() - 1 && y < (int)vec[0].size() - 1) {
memo[x][y] = dfs(x, y + 1, vec) + vec[x][y];
return memo[x][y];
}
if (x < (int)vec.size() - 1 && y == (int)vec[0].size() - 1) {
memo[x][y] = dfs(x + 1, y, vec) + vec[x][y];
return memo[x][y];
}
memo[x][y] = max(dfs(x + 1, y, vec), dfs(x, y + 1, vec)) + vec[x][y];
return memo[x][y];
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
memset(memo, -1, sizeof(memo));
int r, c;
scanf("%d%d", &r, &c);
vector<vector<int>> vec(r, vector<int>(c, 0));
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
scanf("%d", &vec[i][j]);
}
}
printf("%d\n", dfs(0, 0, vec));
}
return 0;
}
大佬,您这递归+记忆化的技术是怎么学出来的,希望能指点一二。