POJ 830. 传球游戏
原题链接
简单
作者:
cocoonnnp
,
2022-03-29 15:29:52
,
所有人可见
,
阅读 146
经典dp问题
//dp[i][j] 传i次球以j为结尾的方法总数
//简单dp问题 想出状态方程和初始条件 基本就解决了!!!
#include <iostream>
using namespace std;
const int N=35,M=35;
int n,m,res=0;
int dp[N][M];
int main(){
cin>>n>>m;
//初始条件
dp[1][n]=1,dp[1][2]=1,dp[0][1]=1;
//递推时要跳过初始条件 从2开始
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(j==1) dp[i][j]=dp[i-1][n]+dp[i-1][j+1];
if(j==n) dp[i][j]=dp[i-1][j-1]+dp[i-1][1];
if(j!=1&&j!=n) dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
}
}
cout<<dp[m][1];
return 0;
}