【动态规划】【记忆化搜索】CODEVS 1010 过河卒 2002年NOIP全国联赛普及组

f(i,j)=f(i-1,j)+f(i,j-1)，显然可以暴力递归求解，但是很多重复的状态，所以可以记忆下来。

注意障碍点和边界的特判。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int x1,y1,x2,y2,dp[25][25];
 5 bool a[25][25];
 6 const int dx[]={1,-1,1,-1,2,-2,2,-2},dy[]={2,2,-2,-2,1,1,-1,-1};
 7 int f(int x,int y)
 8 {
 9     if(dp[x][y]!=-1) return dp[x][y];
10     if(a[x][y]) return dp[x][y]=0;
11     if(x==0) return dp[x][y]=f(x,y-1);
12     if(y==0) return dp[x][y]=f(x-1,y);
13     return dp[x][y]=f(x-1,y)+f(x,y-1);
14 }
15 int main()
16 {
17     scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
18     a[x2][y2]=true;
19     for(int i=0;i<8;i++)
20       {
21           int tx=x2+dx[i],ty=y2+dy[i];
22           if(tx>=0&&ty>=0) a[tx][ty]=true;
23       }
24     memset(dp,-1,sizeof(dp));
25     dp[0][0]=(a[0][0] ? 0 : 1);
26     printf("%d
",f(x1,y1));
27     return 0;
28 }