16. Dynamic Programming, Part 2: LCS, LIS, Coins
ฝัง
- เผยแพร่เมื่อ 5 พ.ย. 2024
- MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Erik Demaine
View the complete course: ocw.mit.edu/6-...
TH-cam Playlist: • MIT 6.006 Introduction...
This is the second of four lectures on dynamic programming. This introduces multiple sequence, substring subproblems, and parent pointers. Three examples of subproblem constraints and expansion are given.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Support OCW at ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s TH-cam and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at ocw.mit.edu/co....
I watch these lectures every few years to refresh my DP. Prof. Demaine is the OG of DP. my favorite
Should pair with Leetcode DP tag as recitation. eg.
2111. Minimum Operations to Make the Array K-Increasing (LIS),
1696. Jump Game VI (speedup via mono-deque for max in sliding window) as AVL in alternating coin.
21:35 "perfectly clear to everyone in the audience?"
> its just 3 MIT staff sitting in the audience, everyon else is at home due to corona
funny man
LCS: 3:50
LIS: 21:48
Alternating Coin Game: 42:44
Locating Man!
I think it is more simple to realize what DP is & how it works & how to use it in 2020 ver. 6.006 , but it is also good to take 2011 DP.
Erik gives different example problem that solve by DP. And that will give you a better understanding of DP.
Link?
@@shadyisaac121 th-cam.com/play/PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb.html
Thanks to MIT and Prof. Erik Demaine!
The last problem's solution (coin game) is minmax search in disguise. DP is isomorphic to DFS on the graph of suproblems, and the graph of subproblems is a graph similar to that of chess moves in this case and the DP recurrence relation is equivalent to minmax search.
19:17 LCS -> DAG
38:12 LIS -> DAG
54:35 COIN -> DAG
LCS: 3:50
LIS: 21:48
Alternating Coin Game: 42:44
How fortunate is that here in India I am able to get education from best university in the world the teachers are truly marvellous. How lucky those students were to be able to interact with such awesome teachers.
Dude! This is just pure gold!
Well, a new version of 6.006. Great work by MIT
This is some god tier content
In my college professors were too lazy to do this(teaching on blackboard without people attending classes)
at 1:32 there is a typo on the board, suffixes of course should start at i and continue to the end, in previous lecture it was written down correctly th-cam.com/video/r4-cftqTcdI/w-d-xo.html
Eric MY GOAT❤
this is so great, honestly thank you - i show my boys and they're mind blown ha ha
If you are getting confused about alternating coin game recurrence like me, th-cam.com/video/Tw1k46ywN6E/w-d-xo.html, minute 54:14 explains the same thing but in little more detail about how the recurrence is derived
Great lecture. Just curious that my implementation of the LCS algorithm returns 5 ("iello") for the longest common subsequence between "hieroglyphology" and "michaelangelo".
I think your aren’t checking for the whole O(n^2) subproblems. That’s why the letter “H” is left.
Thank you so much.... prof.
Erik i was watching 2011 algorithm. You still in mit. You looks older :))
Hard time understanding relation between graphs and answer of problems
52:15
وفوق كل ذي علم عليم
so in the last problem, "you" is choosing the ones that get them smallest amount of coins?
It describes the player that can choose which coin to take. I.e. ˋyou‘ means it is the other player‘s turn.
Hm. How does memoization and tabulation play in with something like the alternating coin game. Your done SRTBOT yes, but thats just a recursive algorithim at the end of the day, not DP. Unless I'm missing something.
Dynamic programming is first and for most about finding a local optimizer for a problem with optimal substructure. The DP part of the solution is the whole min/max bit.
Memoization and tabulation are simply implementation details and not actually a necessary part of solving dynamic programming problems in general (notice when I say "solve" I mean it in the same sense one might use when they solve a differential equation).
However the memoization bit comes into play when you realize that there are choices we can make that ultimately lead us to the same subproblem. For example, if I have:
10 25 30 13 6
We can end up at the substring 25 30 13 in multiple ways. Namely, I choose left, you choose right, then I choose right; or I can choose right, you go left, I go right.
These are all very different choices but lead us to the same subproblem, so the optimal solution for both scenarios is based on the optimal solution for the subproblem 25 30 13.
The tabulation approach is pretty much the same, except we simply begin at the base case, and then fill in the array and read from them.
If you think about it for a bit, you will realize that the tabulation approach actually is the DAG diagram he drew for all of his examples, you would simply reflect it so you start at the base case, and then all the pointers will fill up your tabulated matrix.
Where can i get the notes for this lecture? The option for notes is not present at the lecture page on mit ocw website.
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2020/lecture-notes
empty class room, crazy how 2020 was.
The topoligical order of LIS is for i in 0 to |A| ?
No, the other way. Its considered as a suffix problem and you solve L(0) at the very end.
What is the difference between the DP solution to LIS in this video and BruteForce?
I think brute forcing the LIS takes exponential time.
There was an almost silent memoisation suboptimal usecase) inside the recurse step. While calculating L(i ) you reuse L( j) from memo table. Without that step, the brute force algo would be O( |A| ** 3) algorithm, in my view.
I got HEGLO instead...
I'm still not quite clear about the LCS algo. If we are in the else case (so if A[i] != A[j]) and it turns out that both cases in the max-fkt equally end up in that else case, how does it continue?
If they are both not equal, we explore two other cases : either this character IS in the LCS, meaning the other string's character is not, or vice versa
Is the topology reversed when you go from top down vs bottom up? I'm a bit confused by the topology. Are suffix subproblems always have topology of decreasing i ?
The subproblem dependency graph stays the same, regardless of whether top down or bottom up is used to solve a DP problem. Both bottom up and top down approaches are traversing the same DAG in some topological order.
Are suffix subproblems always have topology of decreasing I ? - I think yes!
Have all students got gastroenteritis? :D
either everyone is home due to corona virus or everyone dropped the class cause they were failing.
should spend more time explaining connection between Graph, shortest path and DP