洛谷P1057传球游戏（逆向递推递归+记忆化）

题目链接：https://www.luogu.org/problemnew/show/P1057

刚看到这道题，就是正向暴力递归暴力出所有情况，而且数据范围这么小，就写了暴力递归，但是。。。tle好几个点。。。

仔细跟着程序走了一遍样例，发现暴力递归过程中好多点都重复计算，重复暴力了，So就改变思维写了逆向递推递归+记忆化ac了

需要注意的是：环，边界处理，有的人用的取余方法，我用的if特判的方法。

暴力递归

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cmath>
 8 using namespace std;
 9 typedef long long ll;
10 typedef unsigned long long ull;
11 const int maxn=1e6+5;
12 int a[maxn];
13 int n,m;
14 int ans;
15 
16 void so(int last,int step)
17 {
18     if(step==m)
19     {
20         if(last==1) ans++;
21         return;
22     }
23 
24     int r=last+1,l=last-1;
25     if(r>n) r=1;
26     if(l<1) l=n;
27     so(r,step+1);
28     so(l,step+1);
29 }
30 
31 int main()
32 {
33     ios::sync_with_stdio(false); cin.tie(0);
34 
35     cin>>n>>m;
36 
37     so(1,0);
38 
39     cout<<ans<<endl;
40 
41     return 0;
42 }

递推递归+记忆化

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cmath>
 8 using namespace std;
 9 typedef long long ll;
10 typedef unsigned long long ull;
11 const int maxn=1e6+5;
12 int a[maxn];
13 int ans[1005][1005];
14 int n,m;
15 int f=0;
16 
17 int so(int last,int step)
18 {
19     //cout<<last<<' '<<step<<endl;
20     if(ans[last][step]!=-1) return ans[last][step];
21     if(step==0)
22     {
23         //if(f==0) cout<<last<<' '<<step<<endl;//方便观察递归出口数据
24         if(last==1) return 1;//或者最好直接ans[last][step]=1;写成1.0更为了方便找递归出口!
25         return 0;//或者最好直接ans[last][step]=0;
26     }
27 
28     int r=last+1,l=last-1;
29     if(r>n) r=1;
30     if(l<1) l=n;
31     int Ans=0;
32     Ans=Ans+so(r,step-1);
33     Ans=Ans+so(l,step-1);
34 
35     ans[last][step]=Ans;
36     return ans[last][step];
37 }
38 
39 int main()
40 {
41     ios::sync_with_stdio(false); cin.tie(0);
42 
43     cin>>n>>m;
44     for(int i=0;i<=1004;i++) for(int j=0;j<=1004;j++) ans[i][j]=-1;//开始bug在这..n范围小了全为0错完..
45 
46     cout<<so(1,m)<<endl;
47 
48     return 0;
49 }

完。