作者FrankTrjpp (請給我前叉)
看板C_and_CPP
標題[問題] 路徑點數問題
時間Mon Jun 8 05:14:13 2009
期末考的考題
一直想不通到底錯在哪邊
┌─┬─┐ 一個表格如右，假設他可用座標來表達位置
│ 3│ 4│ 例如 1在(0,0)的點，2在(0,1)
├─┼─┤
│ 1│ 2│ n*n的正方形表格，表格內的數字為分數(score)
└─┴─┘
只能往右、上、右上走，有負數情況
題目問，走過哪一條路徑，可以使得經過的分數總和為最高，輸出最高分數極可
比如此表格
↑→的分數是1+3+4=8
↗ 的分數是 1+4 =5
→↑的分數是1+2+4=7
因此我們知道最大分數是8
我的做法是
當x為零(1 3這排)，則各點總分可直接加算 (0,0)這點分數是1， (1,0)是1+3=4
當y為零(1 2這排)，則各點總分可直接加算 (0,0) 1 (0,1) 1+2=3
當x>0&&y>0(4這排)，各點總分 考慮該點左方、左下方、下方三點分數
將最大者與自身相加 (4比3、1大，所以挑左邊的4加上本身分數4=8)
請問這樣有什麼問題?
我覺得我只是把遞迴從(0,0)開始寫，然後用while跑遞迴
小測資答案是對的，大測資是錯的
我想知道為什麼會錯(詭論?)
感謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.227.195.24
1F：推 yauhh:因為你用貪婪的算法處理,顧不到全局中最大值的路徑, 06/08 06:20
2F：→ yauhh:你捨棄的區域小路徑仍有可能帶往全局的大路徑 06/08 06:21
3F：推 littleshan:這是典型用 DP 解的問題 06/08 08:10
4F：推 ledia:更新的順序? 簡單解釋一下你的演算法吧 ? 06/08 11:19
5F：→ ledia:DP 即可, 不用去考慮什麼全局、區域的搜尋考量 06/08 11:20
6F：推 Yshuan:graph 自己建圖 最後跑最"長"路徑... 06/08 12:23
7F：→ FrankTrjpp:可以舉個反例嗎@@ 如果方法是錯的至少有1反例吧 06/09 05:42
8F：→ netsphere:那就是遞回寫錯拉 06/09 19:19