P1057传球游戏

这是一道动态规划的水题，难度为提高-。

题意为：n个人围成一个环传球，每一次都可以往左或右传，传m次，问有几种最后传到小明手里的方案数。然后因为一个状态有两个变量，所以我们用dp[][]来存储【传球次数】【当前序号】的方案数，然后我们可以得知每一个最优子结构都是由相邻左边或者右边的两种子结构得来的，所以我们可以得出dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]的方程。再进行特判i==1或i==n即可。

1.分析状态转移方程可以尝试用表格的形式，分析是怎么来的，不拘泥于形式，不一定是max(,)

2.设dp数组时想好状态的完整性

代码

#include<bits/stdc++.h>
#define maxn 35
using namespace std;
int n,m;
int dp[maxn][maxn];//[传球的次数][传到的位置] 
int main(){
    scanf("%d%d",&n,&m);
    dp[0][1]=1;//自己到自己 
    for(int i=1;i<=m;i++){//次数 
        for(int j=1;j<=n;j++){//位置 
            if(j==1){
                dp[i][j]=dp[i-1][n]+dp[i-1][2];
            }
            else if(j==n){
                dp[i][j]=dp[i-1][n-1]+dp[i-1][1];
            }
            else{
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
            }
        }
    }
    cout<<dp[m][1];
    return 0;
}