@[homlin](/user/1281184) 应该会超时。本题正解DP
by hexuchen @ 2024-02-13 11:40:12
@[homlin](/user/1281184)
首先要用long long
其次可以加一个数组做记忆化，以免重复搜索
by wangruiqi36 @ 2024-02-13 13:12:46
@[wangruiqi36](/user/953506)
```#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int n=0,m=0,x=0,y=0;
long long memo[100][100];
bool failOrNot(int zx,int zy)
{
if(zx>n||zy>m)return 1;
if(zx==x&&zy==y)return 1;
if(abs(zx-x)==2&&abs(zy-y)==1)return 1;
if(abs(zx-x)==1&&abs(zy-y)==2)return 1;
return 0;
}
long long fn(int zx,int zy)
{
if(failOrNot(zx,zy))return 0;
if(zx==n&&zy==m)return 1;
if(memo[zx][zy]!=-1)return memo[zx][zy];
memo[zx][zy]=fn(zx+1,zy)+fn(zx,zy+1);
return memo[zx][zy];
}
int main()
{
cin>>n>>m>>x>>y;
memset(memo,-1,sizeof(memo));
cout<<fn(0,0);
return 0;
}
``````
感谢，这个可以快速算出最大96×96的棋盘路线
by homlin @ 2024-02-13 14:19:57
还没学dp。。我马上学
by homlin @ 2024-02-13 14:25:40
同递归3、4超时
by Acce2934 @ 2024-02-22 12:48:36