嗯...

 

题目链接：

 

很明显，这是一道DP题目，其中的状态与阶段都很明显，所以很明显地得出动态转移方程：

f[i][j] = f[i - 1][j - 1] + f[i - 1][j + 1];

 

这个动态转移方程中的第一维表示阶段，第二维表示状态...而且这一题中不要忘记初始化。

将0个人传1次初始化为1...

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 int n, m; 7 int f[35][35]; 8  9 int main(){10     scanf("%d%d", &n, &m);11     f[0][1] = 1;//初始化 12     for(int i = 1; i <= m; i++){13         for(int j = 1; j <= n; j++){14             if(j == 1)15                 f[i][1] = f[i - 1][2] + f[i - 1][n];16             else if(j == n)17                 f[i][n] = f[i - 1][n - 1] + f[i - 1][1];18             else19                 f[i][j] = f[i - 1][j - 1] + f[i - 1][j + 1];20         }21     }22     printf("%d\n", f[m][1]);23     return 0;24 }