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.

, , , , , , , ,

23 thoughts on “Optimal Strategy Game Pick from Ends of array Dynamic Programming

  1. Great video.
    I found the bug in your code:

    33 for(int l = 2; l <= pots.length; l++){
    34 for(int i=0; i <= pots.length – l; i++){
    35 int j = i + l -1;

    should be:

    33 for(int l = 1; l <= pots.length; l++){
    34 for(int i=0; i <= pots.length – l; i++){
    35 int j = i + l;

    since i + l <= pots.length then
    j = i + l – 1 will never check last column

  2. Hi Tushar, there is problem in this solution i tried giving numbers 5,4,1,3,6,2 and got answer (12,9) by picking 5 it should be (10,11) ,because in this scenario you can start from either end first person can never pick more than second,please correct me if i understood wrongly ..thanks for your video +Tushar Roy

  3. 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 ?

  4. 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…. 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *