Junedayday Blog

六月天天的个人博客

0%

Go算法实战 - 10.【圆环回原点问题】

Go-Leetcode

经典面试题 圆环回原点问题

0-12共13个数构成一个环,从0出发,每次走1步,走n步回到0共有多少种走法?

1
2
func CircleToOrigin(n int) int {
}

基础思路

这道题需要一定的动态规划的基础,我们要对这道题做一定的简化,也就是将n变量变成n-1,看看前一步走到了哪。

第n步走到0 = 第n-1步走到12 + 第n-1步走到1

所以,我们要引入一个变量,就是当前走到了哪个位置。用代码表示,就是

result[n][pos] = result[n-1][pos+1] + result[n-1][pos-1]

我们再考虑到pos-1<0的情况,保证处于0到12的范围,代码就更新为:

result[n][pos] = result[n-1][(pos+1+13)%13] + result[n-1][(pos-1+13)%13]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func CircleToOrigin(n int) int {
var result = make([][]int, n+1)
// 初始化
for i := range result {
result[i] = make([]int, 13)
}
// 初始处于原点
result[0][0] = 1
for i := 1; i <= n; i++ {
for j := 0; j < 13; j++ {
// 动态规划
result[i][j] = result[i-1][(j+1+13)%13] + result[i-1][(j-1+13)%13]
}
}
return result[n][0]
}

整个代码实现很清晰。我们可以将这个13提取出来作为一个变量,也就是环的大小可以自行变化。

总结

动态规划最重要的是写出递推的公式,是我们重点需要记忆的部分,剩余的就是考虑边界条件即可。

Github: https://github.com/Junedayday/code_reading

Blog: http://junes.tech/

Bilibili: https://space.bilibili.com/293775192

公众号: golangcoding

二维码