作者haniwang (hani)
看板Grad-ProbAsk
標題[理工] Dynamic programming
時間Thu Feb 7 17:57:09 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549533431.A.A39.html
1F：→ dumpling1234: 第一個是區域 跟 全域 寫反了 02/07 18:29
2F：→ dumpling1234: 第二個 我理解為 avg case worst case 的差別 所以 02/07 18:31
3F：→ dumpling1234: 不一定是只差constant 02/07 18:31
4F：→ eigen555: 像是 quick sort 的 avg 是 nlogn worst 是 n^2 02/07 18:48
5F：→ haniwang: 感謝兩位！ 02/07 21:54
6F：推 ko330: 第一題的敘述是greedy 02/07 21:58
7F：→ Leaving: 樓上不是哦 DP也有optimal substructure 02/07 23:30
8F：→ Leaving: 就是錯在一樓說的地方沒錯 02/07 23:31
9F：推 FlakizK: 第一題的應該是 Dijkstra 的敘述，greedy沒錯 02/08 03:02
10F：→ Leaving: 我的意思是 greedy和DP都有optimal substructure 02/08 06:54
11F：→ Leaving: 所以並不是因為它沒說是greedy才錯 02/08 06:56