f****e
发帖数: 923 | 1 给一个手机键盘（只有0-9，不考虑*#那两个位置）样式的棋盘，骑士初始在数字1的位
置，问走了s步以后（每步走日字），有多少种可能的走法。提示是可以hard code下一
步的位置， 比如1->(6，8)。
followup, 输出所有可能走法
geeksforgeeks 没有搜到类似的 | b***e
发帖数: 383 | | a*******g
发帖数: 1221 | 3 这题我被考过，我上来直接搜，写完了才发现如果只问有多少种走法的话其实是可以直
接DP
由于只有10个键，所以对于每一个键子，你记下所有与这个键子相通的键子的集合。
转移公式举例：zoufa("4",s) = zoufa("3",s-1) + zoufa("9", s-1) + zoufa("0", s
-1)
上式中zoufa("4",s)代表着s步以后骑士在“4”这个键子的走法数。
【在 f****e 的大作中提到】
: 给一个手机键盘（只有0-9，不考虑*#那两个位置）样式的棋盘，骑士初始在数字1的位
: 置，问走了s步以后（每步走日字），有多少种可能的走法。提示是可以hard code下一
: 步的位置， 比如1->(6，8)。
: followup, 输出所有可能走法
: geeksforgeeks 没有搜到类似的
| c********t
发帖数: 5706 | 4 多谢！问一下复杂对是不是 bfs or dfs O(2^S) DP O(10*S)
s
【在 a*******g 的大作中提到】
: 这题我被考过，我上来直接搜，写完了才发现如果只问有多少种走法的话其实是可以直
: 接DP
: 由于只有10个键，所以对于每一个键子，你记下所有与这个键子相通的键子的集合。
: 转移公式举例：zoufa("4",s) = zoufa("3",s-1) + zoufa("9", s-1) + zoufa("0", s
: -1)
: 上式中zoufa("4",s)代表着s步以后骑士在“4”这个键子的走法数。
|
|
