作者jakeasa123 (啊斑斑)
看板Python
标题[问题] 可停留的路线安排程式
时间Wed Nov 30 13:02:18 2016
板上的各位前辈好，小弟最近要写一个包含停留性质的路线安排程式，但想了很久还是没什麽进展……
程式的概念是，有个商人每天能走一格方格，他有ｎ天可以经商，要安排出这ｎ天他能获得最大利益的路线。
经商获利：
┌－－┬－－┬－－┬－－┬－－┐
｜ 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）
如果说不包含停留的问题，可以用有条件性质的导航去找相关的例子，可是加上停留的问题，小弟就不知道还能使用什麽关键字了，自己摸索也得不出结果，所以来此处请教各位前辈是否能给些指点？
先谢谢各位前辈花时间阅读了！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 218.161.49.97
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1480482142.A.713.html
1F：推 Yshuan: DP 实作起来像带state的BFS 11/30 13:05
2F：→ Yshuan: n没过20吧? 然後这应该到prob_solve 11/30 13:06
3F：推 s89227: 搜寻演算法呢？DFS, BFS等等 11/30 13:27
5F：→ s89227: 搜寻演算法，DFS, BFS等等 11/30 13:28
6F：→ Neisseria: 找 longest path problem，把问题转化一下应该可用 11/30 16:34
7F：→ jakeasa123: 感谢前辈，马上去爬文qq！ 11/30 17:56