作者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/cn.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