Principle of Optimality - Dynamic Programming

Today we discuss the principle of optimality, an important property that is required for a problem to be considered eligible for dynamic programming solutions.

[christiansakai]

I love these series, you should definitely make more. There aren't that many good tutorials on the internet about CS

[leixia]

So if you take a glimpse of how Greedy and DP differs, the most noticeable feature is that Greedy is forward processing the question while DP appears to be backward propagation, though this stems from finding the optimal substructure.

[NytronX]

5:10: The proof is so awkwardly trivial that it is hard to wrap my head around, lol.

[---mljd]

We have a graduation project and we have a graph and want to find the optimal path. You saved us from reading lots of dull pages in 10 min. Thank you bro.

[fqwixhg]

Great video! You made this much easier to understand than my textbook

[arunsatyarth]

Was that the correct way to prove it? It sounded like "Prove A is the killer. Imagine B is the killer. but it is not possible because we already stated that A is the killer. So B cannot be the killer."

[amite.]

All the comments here saying this proof is "nonsense" - it's not!
It may look weird and confusing the first time you see this kind of proof, so pay attention and try to follow:
Think of it as if we're given AS A FACT that the route named R from origin city 'a' to destination city 'j' is the shortest.
We're not trying to prove that. It's a given fact!
Now what we actually want to prove is that any sub-route inside R (for example from 'a' to some midpoint 'k' that is located between 'a' and 'j') would ALSO be the shortest route to that midpoint.
And why is that?? Because if there would exist a different route from 'a' to 'k' that is shorter, then you could also use it to improve R and reach faster to the final destination 'j'. But that's a contradiction to the GIVEN FACT that we have in the first place (that R is already the shortest).
Thus you prove that any sub-path within a given shortest path, is ALSO a shortest path....

[ahinst]

Great video! helping college student like me who's just confused why the lecturer explained this so then you just explained it in less than 10 minutes
mksieee pak, saya g ngangong waktu matkul RO. pdhl deadline besok t__T

[why-ak]

great job done brother really loved all your videos . Please make another video for other greedy algorithms and optimal binary search tree!

[johndubchak]

Excellently done. Well worth the simple time investment involved.

[saidelbiev]

I read many comments that the proof doesn't make sense. It does in fact.

The statement to be proved was: R(a.j) is shortest path from a to j IF R(a.k) is shortest path from a to k .

And the proof was not to be made about whether R(a.k) is itself the shortest path from a to k or not. This is another subject. He started where we already knew that R(a.k) is the optimal path from a to k.

The explanation is quite clear. Thanks!

[natiecon]

how about J to H, H to E, E to C and C to A? I think it is also 11.

[tanchienhao]

hi may i know whats the complexity? (im not sure is it O(NE) where N is number of nodes and E is number of edges) if so that means dijkstra is still better?

[lisa]

Good video. Explicit and easy to understand!

[navam]

Please explain how these similar solutions are derived and please note there is one solution with 11 which was missed. See Arturo's comment!

[victoriac]

Wait... I thought at 2:38 that algorithm is Dijkstra's algorithm which is a greedy algorithm? Is it not? I am new to the field so I might be wrong, just wanna check...

[mradulgupta]

Simplest explanation.
Thank you very much

[arturogallobalma]

Ci sono 3 soluzioni:
1) A-D-F-I-J = 3+1+3+4 = 11
2) A-D-E-H-J = 3+4+1+3 = 11
3) A-C-E-H-J = 4+3+1+3 = 11

[albertosivero]

sorry, i have tried with the same approach even in forward and the paths found are the same (even ACEHJ is optimal), can you explain me why forward and backward are the same for this case? thank you