作者jakeasa123 (啊斑斑)
看板Prob_Solve
標題[問題] 可停留的路線安排程式
時間Tue Dec 13 14:56:40 2016
先前在Python板發了篇文，也獲得了一些提示，但看了好幾天也試做了幾個版本，還是沒能達到目標，於是來此詢問。
Python板原文：
https://webptt.com/m.aspx?n=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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1481612204.A.6F8.html
1F：→ freef1y3: 應該就是 DP 了, 可以用第 x 天的獲利推第 x+1 天的獲利 12/13 20:57
2F：→ freef1y3: 若想在第 x+1 天到達 (a,b), 則第 x 天一定要在 12/13 21:00
3F：→ freef1y3: (a-1,b-1) ~ (a+1,b+1) 的九宮格範圍內 12/13 21:01
4F：→ freef1y3: 所以第 x+1 天到達 (a,b) 的最佳獲利, 就可以從第 x 天 12/13 21:03
5F：→ freef1y3: 分別在那九格的獲利算出來 12/13 21:03
6F：推 FRAXIS: 如果選擇停留的話依然有一樣的獲利？ 12/13 21:45
7F：→ bigpigbigpig: 可試試 backtracking 或 Depth-First-Search 演算法 12/14 10:39
8F：→ jakeasa123: 謝謝各位的回應，我再讀些文章試試看！ 12/14 17:57
9F：→ jakeasa123: to:FRAXIS 是的 12/14 17:58
11F：→ Yshuan: for裡面的4個if看方向 再多一個原地停留的段落就是了 12/16 20:38
12F：推 Yshuan: 一開始推文可能害你走錯地方了~ sry~ 12/16 20:43
13F：→ Yshuan: 還有斜走 這樣有9個方向 建議寫一個POINT dir[9]來存 12/16 20:45