※ 引述《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