深搜+记忆化

#include <iostream>
#include <cstring>
using namespace std;
int n, m;
int memo[35][35];
int dfs(int pos, int k)
{
if (k == 0)
return pos == 1 ? 1 : 0;
if (memo[pos][k] != -1)
return memo[pos][k];
int left = pos - 1;
if (left < 1) left = n;
int right = pos + 1;
if (right > n) right = 1;
return memo[pos][k] = dfs(left, k - 1) + dfs(right, k - 1);
}

int main()
{
cin >> n >> m;
memset(memo, -1, sizeof(memo));
cout << dfs(1, m) << endl;
return 0;
}