思路(动态规划)

我们可以想到，再回到0点可以从右面回来，也可以从左面回来，即先到达旁边的一个点，看看有多少回来的方法

即可。所以运用动态规划的思想，我们可以写出递推式如下：

d(k, j) = d(k-1, j-1) + d(k-1, j+1);

d(k, j)表示从点j 走k步到达原点0的方法数，因此可以转化为他相邻的点经过k-1步回到原点的问题，这样将

问题的规模

缩小.由于是环的问题， j-1, j+1可能会超出 0到n-1的范围，因此，我们将递推式改成如下：

d(k, j) = d(k-1, (j-1+n)%n) + d(k-1, (j+1)%n);

因为问题从走k步转化为走k-1步的问题，所以在写程序的时候我们就按照k从0开始递增的循环写，这样当计算第k步的

时候可以直接使用k-1步的结果。

go实现

//n 代表点的个数,k代表bushu
func GetSteps(n int, k int) int {
if n == 0 {
return 1
}
if n == 2 {
if n%2 == 0 {
return 1
} else {
return 0
}
}
var dp [100][100]int
dp[0][0] = 1
for i := 1; i < n; i++ {
dp[0][i] = 0
}
for j := 1; j <= k; j++ {
for i := 0; i < n; i++ {
dp[j][i] = dp[j-1][(i-1+n)%n] + dp[j-1][(i+1)%n]
}
}
return dp[k][0]
}