简单记忆化 -- FatMouse and Cheese HDU - 1078

FatMouse and Cheese HDU - 1078

题意：
给你一个 n * n 的矩阵，每个格子都有一个权值，老鼠可以向上下左右四个方向走，一步可以跨越1 ~ k个格子的距离，但下一个落脚的格子权值要大于现在的落脚格子，老鼠从（0， 0）出发，问老鼠经过格子权值和的最大值是多少。

思路：
显然dfs搜索，但我们可以用数组dp记忆化优化。dp[i][j]表示以（i, j）为落脚点的最优贡献。

code：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1e2 + 5;
int a[maxn][maxn], dp[maxn][maxn];
int n, k;
int dx[4][2] = {
    {
    0, -1}, {
    0, 1}, {
    -1, 0}, {
    1, 0}};void init(){
    memset(dp, -1, sizeof(dp));
}int dfs(int x, int y){
    if(dp[x][y] != -1) return dp[x][y];  //最优贡献已经查找出来了，不需要再重复查找int mx = 0;for(int i = 1; i <= k; i++){
    for(int j = 0; j < 4; j++){
    int xx = x + dx[j][0] * i;int yy = y + dx[j][1] * i;if(xx >= 1 && xx <= n && yy >= 1 && yy <= n && a[xx][yy] > a[x][y])mx = max(mx, dfs(xx, yy));}}return dp[x][y] = a[x][y] + mx;  //记忆化
}int main(){
    while(scanf("%d%d", &n, &k), n != -1 && k != -1){
    for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%d", &a[i][j]);init();   int ans = dfs(1, 1);printf("%d\n", ans); }
}