圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。

输入: 2输出: 2解释：有2种方案。分别是0->1->0和0->9->0

采用动态规划，类似 70. 爬楼梯
走 n 步到 0 的方案数 = 走 n-1 步到 1 的方案数 + 走 n-1 步到 9 的方案数。
由于本题目中有环，所以相关方程需要有取余的步骤。

dp[i][j] = dp[i-1][(j-1+length) % length] + dp[i-1][(j+1) % length]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func backToOrigin(n):  
	// 点的个数为10  
	length := 10  
	dp := make([][]int, n+1)
	for i:= range dp {
		dp[i] = make([]int, length)
	}
	dp[0][0] = 1

	for i:=1; i<n+1; i++ {
		for j:=1; j<length; j++ {
			// dp[i][j]表示从0出发，走i步到j的方案数
			dp[i][j] = dp[i-1][(j-1+length)%length] + dp[i-1][(j+1)%length]  
		}
	}		
	return dp[n][0]