题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1078

思路：

这是一道典型的记忆化搜索模板题。

先介绍记忆化搜索，本质是搜索+DP。

一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。

记忆化搜索（Memory Search），其实还是用递归函数实现的，通常函数名依然叫做dfs。核心语句就是那两部分关键的语句块：

        1.函数一开始的判断出口：if(搜索过) return 数组中的值。因为这里涉及到是否搜索过，所以一般将数组初始化为-1。

        2.函数的递归前进语句：return fib[i]=fib[i-1]+fib[i-2];（没有具体的例子实在不好说了，所以这里用fib数列来做演示）。

这样就做到了数组的每个值只计算了一次，不会有多余的时间消耗。

下面就这道题来讲记忆化搜索基本模板，用dp[i][j]表示从(i,j)出发吃到的cheese最多的值，用(x,y)表示其邻点，则：

dp[i][j]=max(dp[i][j],a[i][j]+dp[x][y])（满足a[x][y]>a[i][j]时）。在这个递推式中，如果dp[i][j]被计算过一次，其值就是最终值，不用再计算。但是如果使用一般的dfs，则会出现大量重复计算一个值的情况，必然会超时。所以采用记忆化搜索，在递推过程中如果一个值被计算过(>=0)，直接返回即可，否则计算其最终值并赋给它。也可以使用DP做这道题，但是要先排序，按照顺序来DP，但比较麻烦。而记忆化搜索则简洁自然许多，其实质当然就是DP。

详见代码：

1 #include
     
       2 using namespace std; 3  4 int n,k; 5 int a[105][105],dp[105][105]; 6 int go[4][2]={-1,0,0,1,1,0,0,-1}; 7  8 int dfs(int x,int y){ 9     if(dp[x][y]>=0) return dp[x][y];10     dp[x][y]=a[x][y];11     for(int i=0;i<4;++i)12         for(int j=1;j<=k;++j){13             int xx=x+j*go[i][0],yy=y+j*go[i][1];14             if(xx>=0&&xx
      
       =0&&yy
       
        a[x][y])15                 dp[x][y]=max(dfs(xx,yy)+a[x][y],dp[x][y]);16         }17     return dp[x][y];18 }19 20 int main(){21     while(~scanf("%d%d",&n,&k)&&n!=-1){22         for(int i=0;i