Dynamic Programming21 sections · 915 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,j−1][i, j-1]. My net: nums[j]−dp[i][j−1][j] - dp[i][j-1]. I pick the better option: dp[i][j]=max⁡(nums[i]−dp[i+1][j],nums[j]−dp[i][j−1])dp[i][j] = \max(\text{nums}[i] - dp[i+1][j], \text{nums}[j] - dp[i][j-1]).