3 3
2
数据规模和约定
40%的数据满足：3<=n<=30，1<=m<=20
100%的数据满足：3<=n<=30，1<=m<=30
明显dp问题，而且比较好想
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 #include <stack> 11 #include <map> 12 #include <sstream> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 const int maxn=1e7+10; 17 using namespace std; 18 19 int dp[50][50];//dp[i][j]表示传i次到j号有多少种方法 20 21 int main() 22 { 23 int n,m; 24 scanf("%d %d",&n,&m); 25 for(int i=1;i<=n;i++)//预处理 26 { 27 if(i==1||(i!=2&&i!=n)) 28 dp[1][i]=0; 29 else 30 dp[1][i]=1; 31 } 32 for(int i=2;i<=m;i++) 33 { 34 for(int j=1;j<=n;j++) 35 { 36 if(j==1) 37 dp[i][j]=dp[i-1][n]+dp[i-1][j+1]; 38 else if(j==n) 39 dp[i][j]=dp[i-1][j-1]+dp[i-1][1]; 40 else 41 dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]; 42 } 43 } 44 printf("%d\n",dp[m][1]); 45 return 0; 46 }
原文：https://www.cnblogs.com/jiamian/p/11872846.html