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沒有關係，放在一起問
而已）
請問這兩個敘述錯在哪邊？
第一個是區域 跟 全域 寫反了第二個 我理解為 avg case worst case 的差別 所以不一定是只差constant
作者: eigen555 (一一一) 2019-02-07 18:48:00
像是 quick sort 的 avg 是 nlogn worst 是 n^2
作者:
ko330 (ko330)
2019-02-07 21:58:00第一題的敘述是greedy
作者: Leaving 2019-02-07 23:30:00
樓上不是哦 DP也有optimal substructure就是錯在一樓說的地方沒錯
作者: FlakizK (Meerkats) 2019-02-08 03:02:00
第一題的應該是 Dijkstra 的敘述，greedy沒錯
作者: Leaving 2019-02-08 06:54:00
我的意思是 greedy和DP都有optimal substructure所以並不是因為它沒說是greedy才錯