I have got a WA in PRVG154 with the following DP states. Can someone please verify if they are correct? The solutions I have seen all contain something different.
I have a structure dp[m][n] in which I have an array v[2]. For Alex’s turn, I use v[0] and for Bob’s turn, I use v[1]
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(i==0 && j==0)
{
dp[i][j].v[0]=A[i][j];
dp[i][j].v[1]=-1000000;
}
else
{
if((i+j)%2==0) //Alex's turn
{
dp[i][j].v[0] = -1000000;
if(i>0)
dp[i][j].v[0] = max(dp[i][j].v[0],A[i][j] + dp[i-1][j].v[1]);
if(j>0)
dp[i][j].v[0] = max(dp[i][j].v[0],A[i][j] + dp[i][j-1].v[1]);
}
else //Bob's turn
{
dp[i][j].v[1] = +1000000;
if(i>0)
dp[i][j].v[1] = min(dp[i][j].v[1],-1*A[i][j] + dp[i-1][j].v[0]);
if(j>0)
dp[i][j].v[1] = min(dp[i][j].v[1],-1*A[i][j] + dp[i][j-1].v[0]);
}
}
}
}