一个环上有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步都卡在那里，等半天算不出，复杂度太高了，大神们给个最优解，面试老师说用动态规划，网上查了但没理解，求助
贴一下思考的成果吧，遗憾阿，要是能在面试时候就做出来该多好！！！
```go
package main
import (
"fmt"
"math/big"
"os"
"strconv"
)
func main() {
fmt.Printf("请输入步数：")
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 <= 0 || testNum%2 != 0 {
fmt.Println("应该输入大于0的偶数")
return
}
fmt.Println("最终结果：", combin(int64(testNum)))
}
func combin(num int64) (ret *big.Int) {
bi := big.NewInt(num)
bh := big.NewInt(num)
bk := big.NewInt(num)
bj := big.NewInt(num)
ret = big.NewInt(0)
for n := num / 10; n >= 0; n-- {
if n > 0 {
ret = bj.Add(ret, bk.Mul(big.NewInt(2), bi.Div(bi.MulRange(10*n+(num-10*n)/2+1, num), bh.MulRange(1, (num-10*n)/2))))
} else {
ret = bj.Add(ret, bi.Div(bi.MulRange(10*n+(num-10*n)/2+1, num), bh.MulRange(1, (num-10*n)/2)))
}
}
return
}
```
#5
更多评论
自己解答一下：抽象化为另一种描述，有N个相同白球，M个相同黑球，排成一列，有多少种排列？这就是一道高中数学的组合问题，相当于从N+M个位置取N个位置放白球
#1
这道题因为是10个单位的环，所以n一定要是偶数才能满足要求，要是奇数个单位的环也可以这样做。那么N和M在这道题里怎么取值呢？首先N+M=n，要么N=M，要么N-M=10*(正整数)，要么M-N=10*(正整数)。（这里隐含条件n应该是不为0的）
0<n<10，n=M+N，只能N=M，有C(2N,N)种排法；
10<=n<20，n=M+N；N=M时，有C(2N,N)种排法；
N-M=10时，有C(N+M,N)种；
M-N=10时，有C(N+M,M)种；
20<=n<30，n=M+N；N=M时，有C(2N,N)种排法；
N-M=10时，有C(N+M,N)种；
M-N=10时，有C(N+M,M)种；
N-M=20时，有C(N+M,N)种；
M-N=20时，有C(N+M,M)种；
#2
今日阅读排行
一周阅读排行