补2：圆环回原点问题

题目

分析

考虑爬楼梯问题，本题和其相似，当你 n 步到 0 点的时候，那么 n-1 步一定是会在 0 点的相邻位置（即 1 和 9 ），所以这是一道动态规划的问题。
那么 dp[i][j] 就表示从 0 点出发，走 i 步到达 j 点的方案数
于是有：dp[i][j] = dp[i-1][(j-1+length) % length] + dp[i-1][(j+1) % length]
其中： dp[i-1][(j-1+length) % length] ：逆时针（后退）
dp[i-1][(j+1) % length] ：顺时针（前进）

代码

#include <iostream>
#include <vector>
using namespace std;

int backToOrigin(int n){
    
	int length = 10;
// 从0点出发走i步到j点的方案数 
	vector<vector<int> > dp(n + 1, vector<int>(length));
	dp[0][0] = 1;
	for(int i = 1; i < n + 1; i++){
    
		for(int j = 0; j < length; j++){
    
// 逆时针（后退）：dp[i-1][(j-1+length) % length]
// 顺时针（前进）： dp[i-1][(j+1) % length]
			dp[i][j] = dp[i-1][(j-1+length) % length] + dp[i-1][(j+1) % length];
		}
	}
	return dp[n][0];
}

int main(){
    
	int n, res;
	cin>>n;
	res = backToOrigin(n);
	cout<<res;
	return 0;
}