A10传球游戏

$题意很简单,所有人编号为 1$~$n围成一圈,每个球只能往左或往右传$
$球初始在1的位置,问你经过m次传递传回来的方案数$

$一.递归(60分)$

$我们可以递归球的位置,当球在第1个位置且递归层数即传递次数为m时,ans加1$
$代码如下$

#include <iostream>
#include <cstring> 
#include <cstdio>
#include <iomanip> 
#include <cmath> 
#include <string>
#include <algorithm>
using namespace std;
long long n,m,ans;
void dfs(long long step,int id){
    if (step==m){
        if (id==1)ans++;
        return;
    }
    if (id==n){
        dfs(step+1,1);
    }else{
        dfs(step+1,id+1);
    }
    if (id==1){
        dfs(step+1,n);
    }else{
        dfs(step+1,id-1);
    }
    return ;
}
int main() {
    cin>>n>>m;
    dfs(0,1);
    cout<<ans;
	return 0;
}

$我们来评估一下这个dfs的时间复杂度$
$不难看出每次递归都会产生两种情况并递归,所以时间复杂度为O(2^m)$
$对于m\le30的数据,肯定会超时,最终得到60分$

$二.递推(动态规划)(100分)$

$主播至今没分清递推和动态规划的区别$
$我们会想到每一个在第i步球在第j个位置的情况,总是会由第i-1步的球在第j+1和j-1的情况变过来的$
$那不妨设dp[i][j]为在第i步球在第j位情况的方案数$
$则dp式为dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]$
$初始状态:很简单因为一开始球必定在1的手上所以dp[0][1]=1$
$注意转移时特判1和n$

1.小练习(补全下列代码)

#include <iostream>
#include <cstring> 
#include <cstdio>
#include <iomanip> 
#include <cmath> 
#include <string>
#include <algorithm>
using namespace std;
long long n,m,dp[50][50];//定义dp[i][j]为在第i步球在第j位的方案数
int main() {
    cin>>n>>m;
    dp[0][1]=1;
    for(int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            if (①)dp[i][j]+=dp[i-1][1];
            else dp[i][j]+=②;
            if (③)dp[i][j]+=dp[i-1][n];
            else dp[i][j]+=④;
        }
    }
    cout<<⑤;
	return 0;
}

①
$A.j==1$
$B.j==n$
$C.i==n$
$D.i==1$
②
$A.dp[i-1][1]$
$B.dp[i-1][j-1]$
$C.dp[i-1][n]$
$D.dp[i-1][j+1]$
③
$A.j==1$
$B.j==n$
$C.i==n$
$D.i==1$
④
$A.dp[i-1][1]$
$B.dp[i-1][j-1]$
$C.dp[i-1][n]$
$D.dp[i-1][j+1]$
⑤
$A.dp[m][n]$
$B.dp[1][n]$
$C.dp[1][m]$
$D.dp[m][1]$

2.正解

#include <iostream>
#include <cstring> 
#include <cstdio>
#include <iomanip> 
#include <cmath> 
#include <string>
#include <algorithm>
using namespace std;
long long n,m,dp[50][50];//定义dp[i][j]为在第i步球在第j位的方案数
int main() {
    cin>>n>>m;
    dp[0][1]=1;
    for(int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            if (j==n)dp[i][j]+=dp[i-1][1];
            else dp[i][j]+=dp[i-1][j+1];
            if (j==1)dp[i][j]+=dp[i-1][n];
            else dp[i][j]+=dp[i-1][j-1];
        }
    }
    cout<<dp[m][1];
	return 0;
}

$时间复杂度O(nm)可过$
$参考答案:BAACD$
$制作不易求点赞$