Not able to understand Optimal Game Strategy Bottom-Up approach

#1

How will we evaluate Optimal Game Strategy Bottom-Up dp.

#2

hello @sahilkhan2312000131

the recurrence relation will remain same,
to build ur dp table start will smallest sub problem , i.e when u have only single element . fill all (i,i) entries of ur dp table with the answer.

then compute result for all 2 size subproblems , with the help of result 1 size subproblem.

repeat this procedure till n size problem.

for reference check this ->

  for (int gap = 0; gap < n; ++gap) {   //deciding size of subproblem
        for (int i = 0, j = gap; j < n; ++i, ++j) { // solving that subproblem , with the help of smaller sub problem 
            // Here x is value of F(i+2, j),
            // y is F(i+1, j-1) and
            // z is F(i, j-2) in above recursive
            // formula
            int x = ((i + 2) <= j)
                        ? table[i + 2][j]
                        : 0;
            int y = ((i + 1) <= (j - 1))
                        ? table[i + 1][j - 1]
                        : 0;
            int z = (i <= (j - 2))
                        ? table[i][j - 2]
                        : 0;
  
            table[i][j] = max(
                arr[i] + min(x, y),
                arr[j] + min(y, z));
        }
    }
  
    return table[0][n - 1];
}
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.