首先是题目的意思：
从一个正方形的0,0点开始走，只能横着走，竖着走，最多走k步，下一个点的数一定要比当前这个点的值大，每走一步，就加上下一个点的数据，问数据最大能有多少。
首先遇到这种题目，走来走去的，一开始想到的是搜索，但是搜索我们搜的很多是路径，能走到那个点的最短路，但是这道题目不一样。
首先要注意的一点是，如果没有条件的搜索，那就是枚举。只有搜遍了才能得到最后的解。
1s题，只是搜的话肯定TLE了。
所以我们想到的自然就是dp了。dp的好处是什么？就是能减少不必要的搜索。用已知的结果减少当前路径搜索的时间。
几个要点：
1、只能从0,0开始走，所以已经减少了很多复杂了，不要傻乎乎的全部循环。
2、注意dfs时候的边界判断。
3、更新值时不要忘记加上当前自己的值。
状态转移方程
dp[][] = max(所有可以从当前点走到的点的dfs的结果集)
初始值肯定是0没问题
最后dp【0】【0】就是结果了。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm> using namespace std;
/*dfs+dp，hdu1078*/ int maps[][];//用来保存原数据
int dp[][];//dp数组
int k;//最多走的步数
int n;//区域大小 int update(int x,int y)
{
int i,j;
int fromX,toX;
int fromY,toY;
int maxTemp=;
int temp; //判断边界条件
if(dp[x][y])
return dp[x][y]; if(x-k < )
fromX = ;
else
fromX = x-k; if(x+k >= n)
toX = n-;
else
toX = x+k; if(y-k < )
fromY = ;
else
fromY = y-k; if(y+k >= n)
toY = n-;
else
toY = y+k; for (i = fromX; i <= toX; i++)
{
if(i!=x && maps[i][y] > maps[x][y])
{
temp = update(i,y);
if(temp > maxTemp)
maxTemp = temp;
}
} for (j = fromY; j <= toY; j++)
{
if(j!=y && maps[x][j] > maps[x][y])
{
temp = update(x,j);
if(temp > maxTemp)
maxTemp = temp;
}
} dp[x][y] = maxTemp + maps[x][y];
return dp[x][y];
} int main()
{
int i,j;//循环变量
int maxNumber=;//记录结果 while (true)
{
cin>>n>>k;
if(n==- && k==-)
break;
memset(dp,,sizeof(dp));
//输入数据
for (i = ; i < n; i++)
for (j = ; j < n; j++)
cin>>maps[i][j]; //只能从0.0点开始走
maxNumber = update(,); cout<<maxNumber<<endl;
} return ;
}