第一次做記憶化搜索的問題 查找了網上的資料 參考了網上對記憶化搜索的解釋  

1.記憶化搜索的思想

記憶化搜索的思想是,在搜索過程中，會有很多重復計算,如果我們能記錄一些狀態的答案，就可以減少重復搜索量

2、記憶化搜索的適用范圍

根據記憶化搜索的思想，它是解決重復計算，而不是重復生成，也就是說，這些搜索必須是在搜索擴展路徑的過程中分步計算的題目，也就是“搜索答案與路徑相關”的題目，而不能是搜索一個路徑之後才能進行計算的題目，必須要分步計算，並且搜索過程中，一個搜索結果必須可以建立在同類型問題的結果上，也就是類似於動態規劃解決的那種。

也就是說，他的問題表達，不是單純生成一個走步方案，而是生成一個走步方案的代價等，而且每走一步，在搜索樹/圖中生成一個新狀態，都可以精確計算出到此為止的費用，也就是，可以分步計算，這樣才可以套用已經得到的答案

3、記憶化搜索的核心實現

a.首先，要通過一個表記錄已經存儲下的搜索結果，一般用哈希表實現

b.狀態表示，由於是要用哈希表實現，所以狀態最好可以用數字表示，常用的方法是把一個狀態連寫成一個p進制數字，然後把這個數字對應的十進制數字作為狀態

c.在每一狀態搜索的開始，高效的使用哈希表搜索這個狀態是否出現過，如果已經做過，直接調用答案，回溯//這個就是標記 優化加速

d.如果沒有，則按正常方法搜索

4、記憶化搜索是類似於動態規劃的，不同的是，它是倒做的“遞歸式動態規劃”。

 

 

FatMouse and Cheese

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8104Accepted Submission(s): 3388


Problem Description   FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he's going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse -- after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.
   
Input   There are several test cases. Each test case consists of

a line containing two integers between 1 and 100: n and k
n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) ... (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), ... (1,n-1), and so on.
The input ends with a pair of -1's.
   
Output   For each test case output in a line the single integer giving the number of blocks of cheese collected.
   
Sample Input  

3 1 1 2 5 10 11 6 12 12 7 -1 -1    
Sample Output  

37    

 

 

 

#include
#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 max_zi,n,k,nx,ny;
int DPS(int x,int y)
{
    int maxx=0;//每次必須初始最大值
    if(vis[x][y]!=0) return vis[x][y];//如果是已經計算過 就不用再計算
    for(int i=0;i<4;i++)//四個方向遍歷
    {
        for(int j=1;j<=k;j++)//每個方向走k個單位
        {
            nx=x+step[i][0]*j;
            ny=y+step[i][1]*j;
            if(nx>=0&&ny>=0&&nxmap[x][y])//新的數一定要大於之前的數 符合題意
                {
                    max_zi=DPS(nx,ny);//找出下一個DFS的最大值
                    maxx=max(maxx,max_zi);//挑選出這個點中遍歷的最大值
                }
            }
        }
    }
    return vis[x][y]=map[x][y]+maxx;//各個方向各個點中最大的數+當前點的數
}
int main(void)
{
    while(~scanf("%d%d",&n,&k))
    {
        memset(vis,0,sizeof(vis));
        if(n==-1||k==-1)
        {
            return 0;
        }
        for(int i=0;i