HDU 1078 胖鼠標與奶酪：記憶化搜索入門經典

記憶化搜索核心思想

• 搜索過程中大量重複子問題，記錄狀態答案避免重複計算。
• 適用於「搜索答案與路徑相關、可分步計算」的問題，類似遞歸式動態規劃。
• 核心實現：哈希表/數組記錄狀態 → 搜索前查表 → 未計算則遞歸 → 存表返回。

問題描述

n×n 格網（n≤100），每格 0-100 塊奶酪。胖鼠從 (0,0) 出發，每步水平/垂直移動 ≤k 格，且目標格奶酪數必須嚴格大於當前格。求最大可吃奶酪總數。

狀態與轉移

• 狀態 (x,y)：當前位置。
• dp[x][y]：從 (x,y) 出發能吃到的最大奶酪數（含當前格）。
• 轉移：四方向各嘗試 1..k 步，目標格在界內且奶酪更多，取最大 dp[nx][ny]。
• dp[x][y] = map[x][y] + max(dp[nx][ny])。

AC 代碼

#include 
#include 
#include 
#define MAX 105
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

int map[MAX][MAX], vis[MAX][MAX];
int step[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int n, k;

int DFS(int x, int y) {
    if (vis[x][y]) return vis[x][y];
    int maxv = 0;
    for (int d=0; d<4; d++)
        for (int s=1; s<=k; s++) {
            int nx = x + step[d][0]*s;
            int ny = y + step[d][1]*s;
            if (nx>=0 && nx=0 && ny map[x][y])
                maxv = max(maxv, DFS(nx, ny));
        }
    return vis[x][y] = map[x][y] + maxv;
}

int main() {
    while (~scanf("%d%d", &n, &k)) {
        if (n==-1 && k==-1) break;
        memset(vis, 0, sizeof(vis));
        for (int i=0; i
測試樣例：3×3，k=1，網格值按行輸入，答案 37。記憶化將指數級搜索優化為 O(n²k) 多項式時間。