先前在Python板发了篇文，也获得了一些提示，但看了好几天也试做了几个版本，还是没能达到目标，于是来此询问。
Python板原文：https://www.ptt.cc/bbs/Python/M.1480482142.A.713.html
程式的概念是，有个商人每天能走零格（停留）或一格（包含斜走）方格，他有ｎ天可以经商，要安排出这ｎ天他能获得最大利益的路线。
经商获利（虽然原要求是1xx*1xx格，这边简化5*5）：
┌－－┬－－┬－－┬－－┬－－┐
｜ 40｜ 30｜ 20｜ 10｜ 95｜
├－－┼－－┼－－┼－－┼－－┤
｜ 50｜ 40｜ 35｜ 30｜ 85｜
├－－┼－－┼－－┼－－┼－－┤
｜ 60｜ 45｜ 起｜ 25｜ 80｜
├－－┼－－┼－－┼－－┼－－┤
｜ 70｜ 10｜ 15｜ 20｜ 75｜
├－－┼－－┼－－┼－－┼－－┤
｜ 80｜ 50｜ 55｜ 65｜ 70｜
└－－┴－－┴－－┴－－┴－－┘ （起点处：25）
如果只有一天，会是往左走停在45；两天的话，会是往右上的30+95；三天的话，30+95+95（停留）……以此类推。
（我知道格子给的数字让这例子很烂QQ）
有想过用循环把“起点～每一格”的最大距离都算出来，可是最边界的方格在中途的自由步数有限和一些原因（满久以前想的，记不起来……），这个方法应该行不通。
自起点开始计算的只会找到每步的最大值，而不是时间内可行走得到的最大值，所以这个应该也行不通。
留言提及的DP看下来是最接近我要求的，只是试了好几次都做不成功，更别说还要记录程式是怎么走的（方向或走到哪格）……
小弟虽是资工的，但教授教得不深（原本还满气教授怎么都教得这么基础，后来想到四年级同班还有人来问我怎么写for和if就开始同情教授了），没有学到很多跟程式有关的；试着在课余时间自学也几年了，但可能方向不对或是没有足够深入，所以现在这个做不出来……
恳请诸位前辈指点！小弟也在此先向前辈致谢花时间阅读与思考！