先前在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就開始同情教授了），沒有學到很多跟程式有關的；試著在課餘時間自學也幾年了，但可能方向不對或是沒有足夠深入，所以現在這個做不出來……
懇請諸位前輩指點！小弟也在此先向前輩致謝花時間閱讀與思考！