PROBLEM LINK DIFFICULTY Easy PREREQUISITES Dynamic Programming PROBLEM IN SHORT Output the smallest n such that the given array can be broken into n contiguous subarrays which are palindromes. SOLUTION This problem has a dynamic programming solution. Simply stated, the constraints are small enough for a $O(n^3)$ solution. If we can somehow find the solution for the subarray from index $i$ to $(n  1)$, and then use it to find subsequent answers  we’ll have a solution. The simplest way to do this, is to define an array $dp$, which stores the answers for each $i$, from $0$ to $(n  1)$. Also, $dp[i] = min(dp[i], dp[j + 1] + 1)$, if the sequence from $i$ to $j$ is a palindrome, for all $j$, from $i$ to $(n  1)$. This is because, if the sequence from i to j is a palindrome, that’s one palindromic sequence and thus we add one to the optimal solution for the array from $(j + 1)$ to $(n  1)$. Finally, $dp[0]$ is the solution, because it’ll be the optimal solution for the array $0$ till $(n  1)$. TIME COMPLEXITY $O(n^3)$ for building the $dp$ array. It can be further optimised to $O(n^2)$ if you find out if the array from $i$ to $j$ is a palindrome using a 2D dynamic programming approach. EDITORIALIST's SOLUTION
This question is marked "community wiki".
asked 26 Dec '17, 20:15

Plz discuss the approach of
also. ie how to make 2D table to check palindrome? answered 03 Sep '18, 07:48

Making a table of palindromes in $O(n^2)$ can be done by extending from each entry "upstream" and "downstream". Note evenlength and oddlength palindromes are found separately. Worst case, of all values the same, will give $\approx n^2/2$ palindromes. Here I tag each palindrome with start element and the element after the end (i.e. to start the next palindrome at) Then finding the "path" to optimally use those palindromes is here also $O(n^2)$ but could probably be $O(n)$ by working breadthfirst.
Amusing observation: I used answered 31 Oct '18, 03:08
Thanks @joffan.
(02 Nov '18, 14:15)

It doesn't necessarily requires a 2d array....... Such is in this case where the given problem can be solved in O(n^{2}) simply by using bottom up instead of top down approach. Here's the link to my submission using the same. answered 25 Sep '18, 18:30
