作者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/m.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