Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 486 Predict the Winner - Transition

Left or right choice

Current player has two choices: take nums[i][i] (left) or take nums[j][j] (right). If I take left: I gain nums[i][i], then opponent plays optimally on [i+1,j][i+1, j]. My net: nums[i]dp[i+1][j][i] - dp[i+1][j]. The subtraction is because opponent's best difference becomes my disadvantage.

If I take right: I gain nums[j][j], opponent plays on [i,j1][i, j-1]. My net: nums[j]dp[i][j1][j] - dp[i][j-1]. I pick the better option: dp[i][j]=max(nums[i]dp[i+1][j],nums[j]dp[i][j1])dp[i][j] = \max(\text{nums}[i] - dp[i+1][j], \text{nums}[j] - dp[i][j-1]).