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

像是 quick sort 的 avg 是 nlogn worst 是 n^2

感謝兩位！

第一題的敘述是greedy

樓上不是哦 DP也有optimal substructure就是錯在一樓說的地方沒錯

第一題的應該是 Dijkstra 的敘述，greedy沒錯

我的意思是 greedy和DP都有optimal substructure所以並不是因為它沒說是greedy才錯