@gormelkumyan3573

There is a tiny mistake in the formula at line 54:13. You can see it by setting i = 1, j = 2, and r = 1, which leads to the expression e[1, 0] + e[2, 2] + ..., where e[1, 0] is undefined. The correct formula can be found in CLRS, Section 15.5, on Optimal Binary Search Trees.

@vishnusingh4118

5:13 Longest Common Palindromic Sequence ( problem 1)
21:55 Second problem (optimal Search Trees) starts
54:14 Alternating Coins Game (3rd and last example)

@RuiLopesFR

If you really want a counter example for 3 nodes, I suggest 1(w=20), 2(w=19), 3(w=18)
Greedy would unbalance the tree in 1->2->3 giving a cost of 112
Optimal solution would give a balanced tree of 1<-2->3 that would cost 95

@tutotechie9043

All of Prof. Devadas lectures are just amazing. In particular, this is probably the best video I watched about DP.

@Hallo.Q

One of the best DP lectures I have ever seen. Thanks to MIT open course ware and Prof. Srinivas Devadas

@brysongalapon877

A counter-example to the greedy optimal BST algorithm using 3 nodes has w1 = 10, w2 = 11, w3 = 12. Cheers!

@Garentei

dp[i, j] = min(dp[i, j], e(i, r-1) + e(r+1, j) + wr * (depth+1)) also works if you add the depth every time you go down the recursion tree.

@prachikhobragade4631

I can see Eric Demaine sitting in the first row at (16:16) , he might be wondering, no subproblems and guessing, just directly the recurrence relation :D

@stormanning1163

Srinivas and Erik you guys are the real Gs!

@adityasahu96

why we need to add all of the node (51:40) i though we need add wr (i<= r <= j)

@mattg9601

"If you go first your guaranteed to not lose". Man goes second and still won.

@SphereofTime

1:20 You can skip some 


1:04:04 dp mazimize

@ariellubonja7856

First example question: the pseudocode shown at 22:33 only works with contiguous palindromes, am I wrong?

Whereas the brain teasers at the start weren’t necessarily contiguous e.g. “rotator” out of “turboventilator”
I do not see how the code can ever figure out “rotator” if you start it with L(0,end)

Also I don’t see why nr. Of subproblems is n squared

@albertoferrada2075

In the last example I don't really understand why should we assume that the second player chooses the min of his options at the moment. Isn't they running a greedy?, it is said that they play optimally, so why don't we model them decision as another dp?

@nanto-x

Erik Demaine 16:17

@anshprakash1778

It was a very good lecture, everything simplified and quite interactive class.Thanks

@xiaomengli8681

The third question should be MinMax problem.

@islams_beauty-c8c

what is wi's and pi's I didn't understand it yet.

@EliotMcLellan

Greedy al gore rhythm sounds like my kind of thing! I use greedy algorithms at my home in my own programs all the time

@loam

One thing I don't get about all those recursions is, why are you guys don't mention that stack is limited and able to hold limited recursive calls to functions, and for some big enough input number for problem to be solved for, you might get stack overflow.
Or is this all just theory and one shouldn't be thinking about how to use it in practice?