刷题使我快乐，满脸开心.jpg

• 来源：CodeTop
• 链接：https://mp.weixin.qq.com/s/NZPaFsFrTybO3K3s7p7EVg

题目

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

示例 1：

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

思路

经典动态规划题了，这个其实就是在爬楼梯的基础上做了下变种，本质没什么改变

动态规划

• dp[i][j] 意为走 i 步到达 j 点的走法数
• 动态方程 dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1] ，当然因为是循环，所以处于防止越界的目的，可以做一下取余操作改为 dp[i][j] = dp[i-1][(j+1)%pointNum] + dp[i-1][(j-1+pointNum)%pointNum]
• 初始化，一步不动也就是 dp[0][0]，它只有一种情况，即 dp[0][0] = 1

动态规划 - 后效性

还有一个注意点是两层循环谁在外层的问题，这个牵扯到动态规划题中不太常见的后效性

认真的需要讨论后效性，目前基本只在比较难的题目和类似谁在外层这种很可能不在意也能写对的地方出现（手动捂脸

至此，细节详见代码注释

代码

// point 点位数，n 步数
func CycleRing(point, n int) int {
	// dp[i][j] 指走 i 步到达 j 点位的走法数
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, point)
	}

    // 初始化
	dp[0][0] = 1

	// i 取值 1 到 n 对应 1 步和 n 步
	// j 取值 0 到 point-1 对应点位 1 和 point
	// 为什么先遍历 步数 ，因为 步数 本就是高步数依赖低步数的结果，不受点位影响
	// 后循环 点位 是因为 点位 在不同 步数 的维度下会影响 走法 结果
	// 即 动态规划的 无后效性
	for i := 1; i < n+1; i++ {
		for j := 0; j < point; j++ {
			// 其实应该是 dp[i-1][j-1] + dp[i-1][j+1]
			// 但是因为是循环点位，为了左右不越界 且 取余后等效，所以进行了取余
			dp[i][j] = dp[i-1][(j-1+point)%point] + dp[i-1][(j+1)%point]
		}
	}
	return dp[n][0]
}