作者jakeasa123 (啊斑斑)
看板Prob_Solve
标题[问题] 可停留的路线安排程式
时间Tue Dec 13 14:56:40 2016
先前在Python板发了篇文，也获得了一些提示，但看了好几天也试做了几个版本，还是没能达到目标，於是来此询问。
Python板原文：
https://webptt.com/cn.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/cn.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