传球游戏(记忆化搜索/dp)

默认的dp
原问题是问最后回到1点的可能方法。
子问题是已知上一部传到各点的方法数，求这一步传到某一点的方法数。
设状态dp[i][j]为在第j步的时候，求传到i的方法数
状态转移方程为dp[i][j]=dp[left][j-1]+dp[right]j+1.
这里给出两种写法。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
int n,m;
int dp[35][35];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(n),read(m);
    dp[1][0]=1;
    rep(i,1,m){
        rep(j,1,n){
            int l=j-1<1?n:j-1,r=j+1>n?1:j+1;
            dp[j][i]=dp[l][i-1]+dp[r][i-1];
        }
    }
    write(dp[1][m]);
    //===========================================================
    return 0;
}

记忆化搜索写法：

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
int n,m;
int dp[35][35];
ll search(int pos,int left){
    if(left==0){
        if(pos==1) return 1;
        else return 0;
    }
    if(dp[pos][left]!=-1) return dp[pos][left];
    int l=pos-1<1?n:pos-1,r=pos+1>n?1:pos+1;
    ll res=0;
    res+=search(l,left-1);
    res+=search(r,left-1);
    return dp[pos][left]=res;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(n),read(m);
    memset(dp,-1,sizeof(dp));
    ll ans=search(1,m);
    write(ans);
    //===========================================================
    return 0;
}