[理工] Dynamic programming

看板Grad-ProbAsk作者 (hani)時間6年前 (2019/02/07 17:57), 編輯推噓2(2推 0噓 9→)
留言11則, 6人參與, 6年前最新討論串1/1
If a dynamic programming problem satisfies the optimal substructure property, then a locally optimal solution is a global optimal. The worst case running time and expected running time are equal to within cons tant factors for any randomized algorithm. （這個敘述跟dp沒有關係，放在一起問 而已） 請問這兩個敘述錯在哪邊？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.0.113 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549533431.A.A39.html
→
02/07 18:29, 6年前 , 1F
第一個是區域 跟 全域 寫反了
02/07 18:29, 1F
→
02/07 18:31, 6年前 , 2F
第二個 我理解為 avg case worst case 的差別 所以
02/07 18:31, 2F
→
02/07 18:31, 6年前 , 3F
不一定是只差constant
02/07 18:31, 3F
→
02/07 18:48, 6年前 , 4F
像是 quick sort 的 avg 是 nlogn worst 是 n^2
02/07 18:48, 4F
→
02/07 21:54, 6年前 , 5F
感謝兩位！
02/07 21:54, 5F
推
02/07 21:58, 6年前 , 6F
第一題的敘述是greedy
02/07 21:58, 6F
→
02/07 23:30, 6年前 , 7F
樓上不是哦 DP也有optimal substructure
02/07 23:30, 7F
→
02/07 23:31, 6年前 , 8F
就是錯在一樓說的地方沒錯
02/07 23:31, 8F
推
02/08 03:02, 6年前 , 9F
第一題的應該是 Dijkstra 的敘述，greedy沒錯
02/08 03:02, 9F
→
02/08 06:54, 6年前 , 10F
我的意思是 greedy和DP都有optimal substructure
02/08 06:54, 10F
→
02/08 06:56, 6年前 , 11F
所以並不是因為它沒說是greedy才錯
02/08 06:56, 11F
‣ 更多 haniwang 的文章
文章代碼(AID): #1SN03tev (Grad-ProbAsk)