Similar to Predict the Winner problem


  • 0
    A

    First let us take a look at Predict the WInner problem,

    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;
        }
    

    Now, we can use the same idea here.

    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];
        }
    

    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. (Made a similar post in Predict the WInner discussion, so that people encountering whichever problem first can relate between these two problems)


Log in to reply
 

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