登录
  • #公开课
  • #入门|算法|数据结构

对动态规划的引入的问题:Stanford Algorithms: Design and Analysis, Part 2 (week3)

吉他的小晴天
1393
2
[backcolor=rgb(250, 250, 250)]I am very lost in this introduction, and ask for help to get the logic.[/backcolor][backcolor=rgb(250, 250, 250)]Here, the professor introduces four ways:1.greedy 2. divide & conquer 3.linear time 4.reconstruction.[/backcolor][backcolor=rgb(250, 250, 250)]For 1.greedy, it may produce a not maxium result. So it's out.[/backcolor][backcolor=rgb(250, 250, 250)]For 2.divide & conquer, it takes exponential time, too slow. So it's out.[/backcolor][backcolor=rgb(250, 250, 250)]Here, it comes my confusion.[/backcolor][backcolor=rgb(250, 250, 250)]I can't figure out the difference between linear time and reconstruction. Why it costs O(n) and What's the fill-in array used for?[/backcolor][backcolor=rgb(250, 250, 250)]Are both of 3.linear time and 4.reconstruction Dynamical Programming?[/backcolor]

[backcolor=rgb(250, 250, 250)]感谢大家的帮助![/backcolor]
2条回复
热度排序

发表回复