[問題] 可停留的路線安排程式

[jakeasa123 (啊斑斑)]

　　先前在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就開始同情教授了），沒有學到很多跟程式有關的；試著在課餘時間自學也幾年了，但可能方向不對或是沒有足夠深入，所以現在這個做不出來……

　　懇請諸位前輩指點！小弟也在此先向前輩致謝花時間閱讀與思考！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.134.106.248
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1481612204.A.6F8.html
→ freef1y3: 應該就是 DP 了, 可以用第 x 天的獲利推第 x+1 天的獲利
→ freef1y3: 若想在第 x+1 天到達 (a,b), 則第 x 天一定要在
→ freef1y3: (a-1,b-1) ~ (a+1,b+1) 的九宮格範圍內
→ freef1y3: 所以第 x+1 天到達 (a,b) 的最佳獲利, 就可以從第 x 天
→ freef1y3: 分別在那九格的獲利算出來
推 FRAXIS: 如果選擇停留的話依然有一樣的獲利？
→ bigpigbigpig: 可試試 backtracking 或 Depth-First-Search 演算法
→ jakeasa123: 謝謝各位的回應，我再讀些文章試試看！
→ jakeasa123:  to:FRAXIS 是的
推 Yshuan: https://goo.gl/nkOhjf 應該是滑雪問題的變形
→ Yshuan: for裡面的4個if看方向 再多一個原地停留的段落就是了
推 Yshuan: 一開始推文可能害你走錯地方了~ sry~
→ Yshuan: 還有斜走 這樣有9個方向 建議寫一個POINT dir[9]來存