# Similar to Longest Palindromic SubSequence

• First let us take a look at Longest Palindromic Subsequence Length problem,

We have to look at longest palindrome length subsequence available for (i,j).
We can break this problem into sub problems like (i, i+1, .... j-1, j). To find (i,j), we need to know data from positions in between
So, we start from smaller length of (i,j) to n
Base case: length 1, i.e. i==j
dp[ i ] [ j ] = 1
case 1: if (i==j),
i.e first letter and last letter are same,
case 1a: if len = 2, dp[i][j] = 2,
case 2a: if len!=2, dp[ i ][ j ] = dp[i+1] [ j -1] + 2, // problem becomes (i, i+1, ..... j, j-1)
case 2: if (i!=j), Math.max( dp[ i ] [ j-1], dp[ i+1 ][ j ] ) // max of dp (i+1 -> j) and dp (i -> j-1), since first and last letter are not same

dp[0][n-1] i.e the problem for (i,j) i=0. j=n-1, (0,n-1) gives the result

Solution:

``````public int longestPalindromeSubseq(String s) {
if (s==null || s.isEmpty()) { return 0;}
int n = s.length();

int[][] dp = new int[n][n];

//dp[i][j] is the length od longest palindromic subsequence for position i to j, inclusive

for (int i=0; i<n; i++) {
dp[i][i] = 1;
}
for (int len = 2; len <=n; len++) {
for (int i=0; i+len-1<n; i++) {
int j = i+len-1;
if (len == 2 && s.charAt(i) == s.charAt(j) ) {
dp[i][j] = 2;
}
else if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] +2;
}
else {
dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
}
}
}
return dp[0][n-1];
}
``````

Now, we can use the same idea here.

At each step, player 1 has the option of choosing between 2 cases:
For any game from position i -> j

1. player 1 chooses i, and leaving i+1 -> j to player 2
2. player 1 chooses j, and leaving i -> j-1 to player 2,

so, in effect we can calculate dp[i][j] for each (i,j) of length from 1 -> n
Base case: if i==j, i.e. for length 1, player 1 always has the first chance of scoring

``````dp[i][j] = nums[i]
``````

Dp formula (from above 2 cases):

``````dp[i][j] = Math.max (nums[i] - dp[i+1][j],   nums[j] - dp[i][j-1])
``````

If, dp[0][n-1] >=0, then player 1 wins, i.e. solution for entire array of scores, (0,n-1)

Solution:

``````public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];

for (int i = 0; i < n; i++) { dp[i][i] = nums[i]; }

for (int len = 2; len <= n; len++) {
for (int i = 0; i+len-1 < n ; i++) {
int j = i + len-1;
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
``````

In both problems, only the elements from and above the diagonal in the dp matrix is calulcated.
For len 1, the mid diagonal elements are calculated
len2, the diagonal elements above the mid-daigonal and so on, until it reaches the top-right, which gives the (0,n-1) value

Hope this is clear.
It will be good if these are added in similar problems.

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