Optimal Strategy Game Pick from Ends of array Dynamic Programming

N pots, each with some number of gold coins, are arranged in a line. You are playing a game against another player. You take turns picking a pot of gold. You may pick a pot from either end of the line, remove the pot, and keep the gold pieces. The player with the most gold at the end wins. Develop a strategy for playing this game.

[sharmilabaskaran]

Thanks for showing how it works. For those who are not clear why he is doing the steps. The basic idea is that with array Player 1 either chooses i or j. Say, Player 1 chooses i. Then player 2 is left with i+1 to j. So, Player 2 can either choose i+1 or j. In this case, the strategy is to take minimum of what player 2 can get so that Player 1 always wins. So the recursion is T[i][j] = Max{(i+Min(T[i+2, j], T[i+1, j-1]), (j +Min(T[i+1, j-1], T[i, j-2])}

[bephrem]

so how do we solve this problem?
yes we will use dynamic programming to solve this problem

[blatogh]

I really hate the other types of explanations that do not have an easily understandable approach thinking process to the problem and then start coding. Yours is awesome, keep working greatly!

[amanpreetsinghbawa]

excellent question & awesome answer
DP works like a magic

[ashishmh]

While this is a decent explanation, I will say its not the best one. With Dynamic Programming, you need to get the intuition across first. Why are we taking a 2D grid, why not 1D array? Its sometimes better to approach these questions with recursion first, then move on to memoizing subproblem results and then coming to this bottom up DP approach.

[arjoojain]

Your videos are very good Tushar.... it's very easy and just by watching it i can code easily... ur way of teaching is very easy and impressive.. u make difficult problems also very easy.... plz keep it up and post more videos as soon as possible.... Thanx a lot for such a nice workkkk.... Keep it up... God bless u.... :)

[lokeshkoliparthi]

Hi, Tushar! I like your videos but in your videos I often see you write the formula directly without explaining how you got that formula specifically to that problem. As in the interview, we can't write the formula directly, I feel that if you add the explanation for formulae you write, it would be helpful and also please explain how to come up with such an approach

Thank You

[binhminhtran]

took me a while to figure out why u had such a formula, but this is still a very helpful video :)

[AlbertLeng]

Thank you Tushar. When will you post more videos?

[aalsicoder]

hey tushar. it would be great if u explain how this problem satisfies the dynamic programming criteria and why you choose dynamic programming to solve this??

[notsoaverageraj]

Thanks a lot Man! So grateful for this one

[saturdaynits]

Good Question and Awesome Explanation.

[lavishgarg]

very nice video tushar, enjoyed a lot and most important, I am grabing the concepts ie how to solve a questions based on the dynamic programming.

[anishsuman]

once u mastered dp and quickly want to see pattern in dp bottom up tabulation then only see his video

[nicolasgoosen]

I think would be easier if he explained it like this:
Each cell contains the best possible results for sequence arr[i]...arr[j] for whoever has first go on that sequence. i.e. if it's the second go, player 2 will have the first go in the remaining sequence.

[jedk]

I was following you while you were doing the matrix, but you lost me when you erased it and just wrote the equations. Using the matrix directly to derive the equations would have been more helpful

[shishirmohire]

Here i am not understanding how both the players are playing in optimized way because we are optimizing the game only for player 1 in every step.

[anandabhinav]

Is it a great explanation or I am dumb?

[jiaweili]

It's the best algorithm tutorial i ever seen!!!

[pal__pal]

you wrote as T [i] [j] . first = max ( T [ i + 1 ] [ j ] . second + val [ i ], T [ i ] [ j -1 ] . second + val [ j ]) i have a difficulty that
1. When you are at i, j position and considering for first then either you can pick "ith" or "jth" item. Let we have chosen "ith" item then why you are considering "second" of remaining ( i+1, j ) items ?