XDU 1056

解法一:简单搜索肯定TLE，只是单纯的想写一发搜索练练手

#include<cstdio>

#include<cstring>

#define maxn 1005

using namespace std;

int i,j,k,n,ans;

int c[maxn][maxn];

int dir[][]={{,},{,}};

bool can(int i,int j)

{

    if(i<||j<||i>n||j>n||i<j||c[i][j]!=)

        return false;

    return true;

}

void dfs(int i,int j)

{

    if(i==n&&j==n)

        ans++;

    else{

        if(can(i,j)){

            c[i][j]=;

            for(int k=;k<;k++){

                int ni=i+dir[][k];

                int nj=j+dir[][k];

                dfs(ni,nj);

            }

        }

        else

            return ;

    }

    c[i][j]=;

//如果当前位置可以走 但是它通往的两个方向都不能走 则不走这一步 还原为0

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        ans=;

        memset(c,,sizeof(c));

        dfs(,);

        printf("%d\n",ans%);

    }

    return ;

 } 

解法2:动态规划

//dp[i][j]表示从(0,0)到达(i,j)有多少种

//dp[i][j]=dp[i-1][j]+dp[i][j-1]

#include<cstdio>

#include<cstring>

#define maxn 1005

using namespace std;

int dp[maxn][maxn];

#define N 10007

int main()

{

    int n;

    dp[][]=;

    for(int i=;i<maxn;i++){

        dp[i][]=;

    }

    for(int i=;i<maxn;i++){

        for(int j=;j<=i;j++){

            dp[i][j]=dp[i-][j]%N+dp[i][j-]%N;

        }

    }

    while(scanf("%d",&n)!=EOF)

        printf("%d\n",dp[n][n]%N);

    return ;

 }