1044 - Palindrome Partitioning

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int T,i,j,l,n,C=1;
    string str;
    cin >> T;
    while(T--)
    {
        cin >> str;
        n = str.length();
        int c[n];
        bool p[n][n];
        for(i=0; i<n; i++)
            p[i][i] = true;
        for(l=2; l<=n; l++)
            for(i=0; i<n-l+1; i++)
            {
                j = i+l-1;
                if(l == 2)
                    p[i][j] = (str[i] == str[j]);
                else
                    p[i][j] = (str[i] == str[j] && p[i+1][j-1]);
            }
 
        for(i=0; i<n; i++)
        {
            if(p[0][i] == true)
                c[i] = 0;
            else
            {
                c[i] = INT_MAX;
                for(j=0; j<i; j++)
                {
                    if((1+c[j]) < c[i] && p[j+1][i] == true)
                        c[i] = 1+c[j];
 
                }
            }
        }
        cout << "Case " << C++ << ": " << c[n-1]+1 << endl;
 
    }
    return 0;
}