作者DJWS (...)
看板ACMCLUB
标题Re: [问题] 10259 Hippity Hopscotch
时间Fri Feb 25 17:48:59 2005
※ 引述《JonathanWang (小尹)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 但是呢 我总觉得这个方法很没有效率 ^^"
: : 这个方法就跟 BFS + memorization 差不多吧
: : 也不像是DP
: : 我想应该会有更好的方法吧
: BFS + memorization ...
: 我认为这算是 DP 的一种耶
soga
我一直以为是不一样的东西 ^_^">
我初次看到这题目, 就觉得应该是用BFS来做
最多可走100步 (一定要走到penny比原来多的格子 penny范围最大到100)
每走一步会有4k种选择 (最大也只到 直的99种 + 横的99种 = 198种)
由於可以用题目条件 以及用memorization 来挡掉不少情形
BFS应该是跑得完啦 不过我估不出时间复杂度是多少 :p
後来我看到讨论区有人说这一题可以用DP解决
於是让我纳闷了很久
难道存在着神奇的三层回圈 可以把答案算出来?
既然 BFS + memorization 是 DP 的一种
那我就不用想太多啦 ^^
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.122.26.5