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

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

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

#include cstdio
#include cstring
using namespace std;
int x1,y1,x2,y2,dp[][];
bool a[][];
const int dx[]={,-,,-,,-,,-},dy[]={,,-,-,,,-,-};
int f(int x,int y)
{
if(dp[x][y]!=-) return dp[x][y];
if(a[x][y]) return dp[x][y]=;
if(x==) return dp[x][y]=f(x,y-);
if(y==) return dp[x][y]=f(x-,y);
return dp[x][y]=f(x-,y)+f(x,y-);
}
int main()
{
scanf("%d%d%d%d", x1, y1, x2, y2);
a[x2][y2]=true;
for(int i=;i i++)
{
int tx=x2+dx[i],ty=y2+dy[i];
if(tx = ty =) a[tx][ty]=true;
}
memset(dp,-,sizeof(dp));
dp[][]=(a[][] ? : );
printf("%d\n",f(x1,y1));
return ;
}