You are not logged in. Please login at to post your questions!


ZCO15001 - Editorial






Dynamic Programming


Output the smallest n such that the given array can be broken into n contiguous sub-arrays which are palindromes.


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[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)$.


$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.


#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[i]);
    printf("%d", recur(0));
    //for (int i = 0; i < n; i++)
    //  printf("%d ", recur(i));
    //printf("\n %d", isPalin(3, 4));
    return 0;
This question is marked "community wiki".

asked 26 Dec '17, 20:15

brahmnoor's gravatar image

accept rate: 0%

edited 24 Jan '18, 20:22

admin's gravatar image

0★admin ♦♦

Plz discuss the approach of

It can be further optimised to O(n2) if you find out if the array from i to j is a palindrome using a 2D dynamic programming approach.

also. ie how to make 2D table to check palindrome?


answered 03 Sep '18, 07:48

jvjplus's gravatar image

accept rate: 0%

Can someone tell this please?

(24 Oct '18, 17:55) the_extractor4★

Making a table of palindromes in $O(n^2)$ can be done by extending from each entry "upstream" and "downstream". Note even-length and odd-length 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 breadth-first.


n = int(input())
seq = list(map(int, input().split()))

ps = [[] for _ in range(n)]

# find all palindromes
for mid in range(n):
    up = dn = mid
    while up >= 0 and dn < n:
        if seq[up] != seq[dn]:
        up -= 1
        dn +=1
    up = mid
    dn = mid+1
    while up >= 0 and dn < n:
        if seq[up] != seq[dn]:
        up -= 1
        dn +=1

#find best set of palindromes for traverse
pto = [n+1]*(n+1)
pto[0] = 0
for fx in range(n):
    for p in ps[fx]:
        if pto[p] > pto[fx] + 1:
            pto[p] = pto[fx] + 1


Amusing observation: I used dn as an abbreviation for "down" and noticed that it's up, upside-down :-)


answered 31 Oct '18, 03:08

joffan's gravatar image

accept rate: 13%

Thanks @joffan.

(02 Nov '18, 14:15) the_extractor4★

It doesn't necessarily requires a 2d array.......

Such is in this case where the given problem can be solved in O(n2) 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

darklord_chef's gravatar image

accept rate: 0%


I'll have a look in Jan 2020, when the "competition" ends. :-)

(31 Oct '18, 03:09) joffan5★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 26 Dec '17, 20:15

question was seen: 895 times

last updated: 23 Nov '18, 13:37