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才错