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