**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 sub-arrays 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 sub-array 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* = min(dp*, 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**

```
#include <bits/stdc++.h>
using namespace std;
int n, a[307];
int dp[307];
int isPalin(int i, int j) { // is the sequence from i to j a palindrome - including both i and j
int length = j - i + 1;
for (int it = 0; it < length/2; it++) {
if (a[i + it] != a[j - it])
return 0;
}
return 1;
}
int recur(int cur) {
if (dp[cur] != -1)
return dp[cur];
else {
int ans = INT_MAX;
for (int i = cur; i < n; i++) {
if ( isPalin(cur, i) )
ans = min(ans, recur(i + 1) + 1);
}
return dp[cur] = ans;
}
}
int main() {
memset(dp, -1, sizeof(dp));
scanf("%d", &n);
dp[n] = 0;
dp[n - 1] = 1;
for (int i = 0; i < n; i++)
scanf("%d", &a*);
printf("%d", recur(0));
//for (int i = 0; i < n; i++)
// printf("%d ", recur(i));
//printf("
```

%d", isPalin(3, 4));

return 0;

}