# My Recursive DP Solution is getting a TLE. Can someone please help me understand the complexity of my solution?

• So I have been at this for a while. And I need help understanding the complexity of my approach. Also I looked around at other people's solutions and no one seems to have approached this from a recursive standpoint. Is there a reason why a recursive DP solution is not the best idea?

``````import java.util.Hashtable;
public class Solution {
public class Pair {
public int i;
public int j;
public Pair(int i, int j) {
this.i = i;
this.j = j;
}
}
public Pair helper(String s, int low, int high, Pair[][] history, int len, int strLow, int strHigh) {
if(history[low][high]!=null) {
if(strHigh - strLow + 1 == len + history[low][high].j - history[low][high].i + 1)
return new Pair(strLow, strHigh);
else
return history[low][high];
}

if(low==high || (low > high && len>0)) {
return new Pair(strLow, strHigh);
}

if(low>high) {
return new Pair(-1, -1);
}

Pair res = null;
if(s.charAt(low)==s.charAt(high))
res = helper(s, low+1, high-1, history, len+2, strLow, strHigh);

if( res==null || (res.j - res.i  < high - low )) {
Pair res1 = helper(s, low, high-1, history, 0, low, high-1);
Pair res2 = helper(s, low+1, high, history, 0, low+1, high);
Pair temp = (res1.j - res1.i >= res2.j - res2.i)? res1 : res2;
res = (res!=null && res.j - res.i >= temp.j - temp.i)? res : temp;
}
history[low][high] = res;
return history[low][high];
}

public String longestPalindrome(String s) {
if(s.length() <=1) {
return s;
}
Pair res = helper(s, 0, s.length()-1, new Pair[s.length()][s.length()] ,  0, 0 , s.length()-1);
return s.substring(res.i, res.j + 1);

}
}
``````

• This post is deleted!

• This post is deleted!

• @yixuanwang.start Thank you! I appreciate it. I'll try and read up more on DP :)

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