记忆化搜索=搜索+动态规划
有关更多资料，请访问(热心博客) https://blog.csdn.net/hjf 1201/article/details/78680814
这里介绍一个水问题。 ((可水可水) )，~~ http://poj.org/problem？ id=1678
传统游戏在n个号码池中的两个玩家之间进行。 没有必要一定要区分。
第一个玩家从池中选择[a，b]的数字x1(0ab )。 这意味着a=x1=b。 然后，第二个玩家必须选择数字y1，使y1-x1位于[a，b] (这是a 0 )，因此意味着y1 x1。 然后，第一个玩家应该选择数字x2，使得x2-y1位于[a，b] …之中。 如果其中一个不能选择，游戏就结束。 请注意，玩家不能跳牌。
玩家的得分取决于他选择的数字。 顺便说一下，玩家1score=x1x2…玩家2score=y1y2…
假设玩家1、2完美地进行了游戏，对于玩家1，能获得的最高得分差是多少(玩家1score-玩家2score )。
第一行包含表示测试用例数的整数t(1=t=20 )。 然后根据t的情况。 每个案例正好包含两行。 第一行包含三个整数n、a和b (2=n=10000，0ab=100 )。 第二行包含n个整数(池中的数字)，它们都位于[-9999，9999 ]中。
请为每个输出打印player1获得的最大分数差异。 请注意，负数也可以。 也就是说，只要玩家2玩得完美，玩家1就不会赢。
样本输入
3 6 1 2 1 3 -2 5 -3 6 2 1 2 -2 -1 2 1 2 1 0个样品输出
- 301 # include iostream # include algorithm # includecstdiousingnamespacestd； #define INF0x3f3f3f3fint n、a、b； int num[10005]，s[10005]； //s【i】排列是，最初取的数为I的情况下的最大差boolcheck(intx ) (if ) x=ax=b ) return 1； 返回0； (intDFS ) intI ) if ) s[I]！=-INF(returns[I]； int mx=-INF； for(intj=I1； jn； j () if ) check(num[j]-num[I] ) MX=max(MX，DFS ) j ) )； (if ) MX==-INF ) mx=0； s[i]=num[i]-mx； 返回s [ I ]； (}int main ) ) { int t； 扫描(' % d '，t )； while(t-- ) Scanf ) ' %d%d ) d )，n，a，b )； for(intI=0； in； I ) Scanf('%d”，num[i]； s[i]=-INF； }sort(num，num n )； int ans=-INF； for(intI=0； in； I ) if (检查(num ) I ) ) ans=max ) ans，DFS ) I )； (if ) ans==-INF ) ans=0； printf(%d(n )、ans )； }返回0； )以及杭电1428做了一个长时间不会交流的该死的优秀主题
主题如下
LL最近沉迷于交流，无法自拔，每天都是卧室、机房的2点1分。 因为长时间坐在电脑旁边，所以运动不足。 他决定充分利用从卧室到机房的时间，在校园里散步。 整个HDU校园呈方形，分为n*n个小方格，代表每个区域。 例如，LL所在的18号宿舍位于校园西北角，即方格(1，1 )为代表的地方，机房所在的第三实验楼位于东南端的) n，n )。 由于可以选择多条路线，LL希望每次的散步路线不同。 另外，他认为从a区域到b区域，只有在有从b到机房的路线的情况下，才比从a到机房的路线更近。 否则，你可能永远也到不了机房…)。 现在他想知道的是，满足要求的所有路线总共有多少条。 你能告诉他吗？
Input各组测试数据的第一行为n(2=n=50 )，接下来的n行每行有n个，表示通过各个区域所需的时间t ) t(0t=50 )。 因为卧室和机房在3楼，所以起点和终点也需要时间。
Output对各组的测试数据输出总路由数(小于2^63 )。
样本输入
31 2 31 2 31 2 331 1 11 1 11 1 1 simple
out1
6
用bfs求数组中每一点到终点的最短距离，然后用DFS记忆化搜索，条件就是在step数组中从起点到终点的每一步都是要递减的。
#include<iostream>#include<cstdio>#include<algorithm>#include<queue>#include<cstring>#define INF 100000000using namespace std;typedef long long ll;struct stu{ int a,b;};int n;ll arr[52][52];ll step[52][52];ll dp[52][52];int d[4][2]={1,0,0,1,0,-1,-1,0};void bfs(int x,int y){ queue<stu>que; que.push({x,y}); step[x][y]=arr[x][y]; while(que.size()){ int xx=que.front().a; int yy=que.front().b; que.pop(); for(int i=0;i<4;i++){ int dx=xx+d[i][0]; int dy=yy+d[i][1]; if(dx>=1&&dy>=1&&dx<=n&&dy<=n){ if(step[dx][dy]>step[xx][yy]+arr[dx][dy]){ step[dx][dy]=step[xx][yy]+arr[dx][dy];//更新step数组，使他保存较小的的距离 que.push({dx,dy}); } } } } }ll dfs(int x,int y){ if(dp[x][y]) return dp[x][y]; else { for(int i=0;i<4;i++) { int dx=x+d[i][0]; int dy=y+d[i][1]; if(dx>=1&&dy>=1&&dx<=n&&dy<=n) { if(step[dx][dy]<step[x][y]) dp[x][y]+=dfs(dx,dy);//只有发生回溯的时候才会更新dp数组，并且会按照路径回溯，只有当(x,y)有多个方向满足条件时，才会发生叠加，即有对多条路径可以选择； } } } return dp[x][y];}int main(){ while(cin>>n) { for(int i=0;i<=50;i++){ for(int j=0;j<=50;j++) step[i][j]=INF; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>arr[i][j]; } } bfs(n,n); memset(dp,0,sizeof(dp)); dp[n][n]=1;//终点初始化为1，因为只有走到终点才会发生回溯。（即无路可走了就会发生回溯） cout<<dfs(1,1)<<endl; } return 0;}二维系列的记忆化搜索
#include<bits/stdc++.h>using namespace std;int n,k;int xx,yy;int mp[101][101],vis[101][101]; FatMouse and Cheeseint check(int x,int y){if(x<0||x>=n||y<0||y>=n) return 0;return 1;}int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};int dfs(int x,int y){if(vis[x][y]!=-1) return vis[x][y];vis[x][y]=0;int temp=0;for(int i=0;i<4;i++){for(int j=1;j<=k;j++){xx=x+dx[i]*j;yy=y+dy[i]*j;if(check(xx,yy)&&mp[xx][yy]>mp[x][y]){temp=max(temp,dfs(xx,yy));}}}vis[x][y]=temp+mp[x][y];return vis[x][y];}int main(){while(cin>>n>>k){if(n==-1&&k==-1) break;for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%d",&mp[i][j]);}}memset(vis,-1,sizeof(vis));cout<<dfs(0,0)<<endl;}return 0;} #include <stdio.h> //How many ways#include <string.h>#include <algorithm>using namespace std;int n,m,dp[105][105],a[105][105];int check(int x,int y) {if(x<1 || x>n || y<1 || y>m)return 1;return 0;}int dfs(int x,int y) {if(dp[x][y]!=-1) return dp[x][y];int temp=0;dp[x][y] = 0;for(int i = 0; i<=a[x][y]; i++) {for(int j = 0; j<=a[x][y]-i; j++) {if(!check(x+i,y+j)) {temp+=dfs(x+i,y+j);temp=temp%10000;}}}dp[x][y]=temp;return dp[x][y];}int main() {int t,i,j;scanf("%d",&t);while(t--) {scanf("%d%d",&n,&m);for(i = 1; i<=n; i++)for(j = 1; j<=m; j++)scanf("%d",&a[i][j]);memset(dp,-1,sizeof(dp));dp[n][m] = 1;printf("%dn",dfs(1,1));}return 0;}