一个环上有10个点，编号为0-9,从0点出发，每步可以顺时针到下一个点，也可以逆时针到上一个点，求：经过n步又回到0点有多少种不同的走法？
举例：n=1, 0->1或者0->9,回不到0点，共0种走法；n=2, 0->1->0, 0->1->2, 0->9->0, 0->9->8, 有2种走法回到0点
```go
package main
import (
"fmt"
"os"
"strconv"
)
var result = 0
func main() {
var buffer [512]byte
n, err := os.Stdin.Read(buffer[:])
if err != nil {
fmt.Println(err)
return
}
testNum, err := strconv.Atoi(string(buffer[:n-1]))
if err != nil {
fmt.Println(err)
return
}
if testNum%2 != 0 {
fmt.Println(testNum, " is not Oushu")
return
}
step(testNum, 0)
fmt.Println(result)
}
func step(num int, record int) {
num--
if num < 0 {
return
} else {
record++
if num == 0 {
if (record+num*10)%10 == 0 {
result++
}
}
step(num, record)
record -= 2
if num == 0 {
if (record+num*10)%10 == 0 {
result++
}
}
step(num, record)
}
}
```
上面我用迭代写的，但是算100步都卡在那里，等半天算不出，复杂度太高了，大神们给个最优解，面试老师说用动态规划，网上查了但没理解，求助
有疑问加站长微信联系（非本文作者）
