Java DP solution 6ms


  • 0
    J

    This is a classical "coins in a line" question. dp[i][j] represents the maximum score a player can get in the range of i to j of the nums array.
    for(int i = 0; i < len; i++) {
    dp[i][i] = nums[i];
    }
    for(int i = 1; i < len; i++) {
    for(int j = 0; i + j < len; j++) {
    dp[j][j + i] = Math.max(sum[j][i + j - 1] - dp[j][i + j - 1] + nums[i + j],
    sum[j + 1][i + j] - dp[j + 1][i + j] + nums[j]);
    }
    }
    the result is dependent on whether dp[0][len - 1] > sum[0][len - 1] / 2.0


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.