Longest Palindrome Subsequence Looping

Question

I was reading about Longest Palindrome Subsequence algorithm and came across this video :- Video

And also came across this blog for the dynamic program code for this problem. Ajeet Singh

Here is the code from the above link :-

public static int getLongestPalindromicSubSequenceSize(String source){
    int n = source.length();
    int[][] LP = new int[n][n];

    //All sub strings with single character will be a plindrome of size 1
    for(int i=0; i < n; i++){
        LP[i][i] = 1;
    }
    //Here gap represents gap between i and j.
    for(int gap=1;gap<n;gap++){   //-------> 1
        for(int i=0;i<n-gap;i++ ){// --------> 2
                    int j=i+gap; // ---------> 3
                    if(source.charAt(i)==source.charAt(j) && gap==1)
                        LP[i][j]=2;
                    else if(source.charAt(i)==source.charAt(j))
                        LP[i][j]=LP[i+1][j-1]+2;
                    else
                        LP[i][j]= Math.max(LP[i][j-1], LP[i+1][j]);              
         }      
    }       
    return LP[0][n-1];      
}

In the above code I have marked three lines as 1, 2 and 3. I am unable to understand those to loops . My doubts :-

1)In the first loop he has initialized an integer called gap to 1 . Why did he initialize it to 1 and why not 0 ?

2) In the second for loop , i<n-gap , why did he do that ?

3) int j=i+gap why this again?

I am new to Java and I have a problem in understanding them . Kindly can anyone please explain these three lines of code .

Thanks

Answer 1

1. You have an nxn matrix that stores the results of the subproblems. He is marking the diagnal of this matrix in the block above your question 1. This block says that every character is a palindrome of size 1. Setting the gap = 1 to start means he is not going to retest single characters, but rather start looking at substrings of length == 2
2. You need to move the left index of the string up through the input string until its position plus the substring you are testing's length is still in the valid range of character indices. This is to prevent index of bounds exceptions
3. He is picking the right bound of the substring he is going to test for palindrome-ness