# TLE in Dynamic Programming solution Java Code

• Hi,
I am getting TLE for this DP Solution can anyone suggest some Improvement.

``````public class Solution {
public int minCut(String str) {
int n = str.length();

/*C[i][j] = Minimum number of cuts needed for palindrome partitioning
of substring str[i..j]
P[i][j] = true if substring str[i..j] is palindrome, else false
C[i][j] is 0 if P[i][j] is true */

int C[][] = new int[n][n];
boolean P[][] = new boolean[n][n];

// Every substring of length 1 is a palindrome

for (int i = 0; i < n; i++) {
C[i][i] = 0;
P[i][i] = true;
}

/* L is substring length. Build the solution in bottom up manner by
considering all substrings of length starting from 2 to n.*/

for (int L = 2; L <= n; L++) {

// If L is 2, then  just need to compare two characters. Else
// need to check two corner characters and value of P[i+1][j-1]

for (int i = 0; i < n - L + 1; i++) {
int j = i + L - 1;
if (L == 2) {
P[i][j] = (str.charAt(i) == str.charAt(j));

} else {
P[i][j] = (str.charAt(i) == str.charAt(j))
&& P[i + 1][j - 1];
}
if (P[i][j] == true) {
C[i][j] = 0;
} else {
C[i][j] = 10000;

// Make a cut at every possible localtion starting from i to j,
// and get the minimum cost cut.

for (int k = i; k <= j - 1; k++)
C[i][j] = Math.min(C[i][j], C[i][k] + C[k + 1][j] + 1);
}
}
}
return C[0][n-1];
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.