※ 引述《sophialiege (別忘了)》之銘言：
: Sorry for I only can type in English.
沒關係 如果有看不懂的單字 我可以查字典 :p
: The key point is we can jump from grid 'a' to grid 'b', if and only if
: the pennies 'a' possess more than that 'b' possess.
: For example, 1 ? ? k is 2
: 4 2 5
: 3 ? ?
: Assume we're now at (1,0) which has 4 pennies.
: By the capacity property, 1 2 5 3 is possible to move onto.
: By the property you ignored, only 5 is possible to move onto.
: The reason is 5 is larger than 4, current square pennies.
我想到一個方法:
開一個table, 用來紀錄每一個位置的最大值. 初始值都是零；
令 table[左上角] = 左上角那格的pennies;
while (只要有任何一個位置 a, 從這個位置可以合法的移動到 b
&& table[a] + b的pennies > table[b]
&& table[a] != 0 )
{
table[b] = table[a] + b的pennies;
}
找尋table的最大值, 即為答案；
但是呢 我總覺得這個方法很沒有效率 ^^"
這個方法就跟 BFS + memorization 差不多吧
也不像是DP
我想應該會有更好的方法吧
--
如果題目規定說 只能向右和向下跳
這個問題就很好解決了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.26.5