题解 | #[NOIP2008]传球游戏#

一、判断是否可以用递归

1.原问题：

小球从小曼手里传出去经过三次传递又回到小曼手里的可能方案数。

子问题：

从1开始传球第i次传递时到达j的手里的方法数

符合具有相同子问题的条件

2.符合最优决策：

3.解决当前的决策与之前怎么决策的没有关系

满足无后效性

二、递推公式易错，因为是环形站位，所以还要注意取模，并且是从1开始，与平常的循环的写的方式不一样，要推一下怎么写。

三、每次传递可以由左边那个人传递过来，也可以从右边。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int M=50;
long long dp[M][M];
int main(){
    cin>>n>>m;
    dp[0][1]=1;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=dp[i-1][((j-2+n)%n)+1]+dp[i-1][((j+n)%n)+1];
        }
    }
    cout<<dp[m][1]<<endl;
    return 0;
}