title: Dynamic Programming to find all palindromic substrings
body: <p>I was trying to solve a question via dynamic programming. I have a string and I need to find all the possible palindromic substrings. Say, I have a string of length <code>n</code>. I have created a matrix <code>n*n</code> for the lookup. A cell <code>(i,j)</code> is either 1 or 0. If it is 1, it means that the substring[i..j] is a palindrome, otherwise 0. Initially the diagonals are 1 because every character itself is a palindrome.</p>
  
  <p>I need to fill the matrix properly as stated above.</p>
  
  <p>I figured out the following:</p>
  
  <ol>
  <li>If substring[i..j] is a plaindrome, then I can find if substring[i-1..j+1] is palindrome in <code>O(1)</code> time by checking if matrix[i][j]==1 and word[i-1] == word[j+1]..</li>
  </ol>
  
  <p>How can I go about filling the matrix, for other general cases.</p>
  
  <p><strong>A small explanation with pseudocode/language specific implementation to fill out the matrix will be much appreciated</strong></p>
  
  <p><a href="https://i.stack.imgur.com/HAy85.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/HAy85.png" alt="Initial Matrix"></a></p>
  
  <p>Edit: I need some explanation as to how and in which order the matrix gets filled (i.e diagonally, horizontally etc) . I want to solve the question by filling out this matrix only, and by no other method. My question is not a duplicate of <a href="https://stackoverflow.com/questions/19801081/find-all-substrings-that-are-palindromes">this</a> </p>