作者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