Why is this happening, please i have been stuck on this for a day now. I've searched everywhere. This is the problem DP problem -> Palindrome partitioning
I couldn't solve it and looking at solutions i couldn't understand why some solution pass and some do not, Please help me with it. I want to understand why iterative gives TLE and recursive solution passes.
Thanks.
Iterative code ->
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<int>>dp(n,vector<int>(n));
vector<vector<int>>ck(n,vector<int>(n));
for(int i=0;i<n;i++) ck[i][i]=1;
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++) {
if(j-i==1&&s[i]==s[j]) ck[i][j]=1;
else ck[i][j]=ck[i+1][j-1]&&(s[i]==s[j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) {
if(ck[i][j]||(i==j)) dp[i][j] = 0;
else dp[i][j] = j-i;
}
}
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
if(ck[i][j]) {
dp[i][j]=0;
continue;
}
for(int k=i;k<j;k++){
if(ck[i][k]) dp[i][j]=min(dp[i][j],1+dp[k+1][j]);
}
}
}
return dp[0][n-1];
}
};
This code doesn't work fine and gives TLE.
class Solution {
public:
int solve(string &s,vector<vector<int>>&dp,vector<vector<int>>&ck,int i, int j){
int n = s.size();
if(i>=j) return 0;
if(dp[i][j]!=-1) return dp[i][j];
if(ck[i][j]) return dp[i][j] = 0;
int val = j-i;
for(int k=i;k<=j;k++){
if(ck[i][k]) val = min(val,1+solve(s,dp,ck,k+1,j));
}
return dp[i][j] = val;
}
int minCut(string s) {
int n = s.size();
vector<vector<int>>dp(n,vector<int>(n,-1));
vector<vector<int>>ck(n,vector<int>(n));
for(int i=0;i<n;i++) ck[i][i]=1;
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++) {
if(j-i==1&&s[i]==s[j]) ck[i][j]=1;
else ck[i][j]=ck[i+1][j-1]&&(s[i]==s[j]);
}
}
return solve(s,dp,ck,0,n-1);
}
};
This code works fine and beats 90% of users on leetcode.
why is this happening, please i have been stuck on this for a day now. I've searched everywhere.
Thanks!
9q3418
9q3419
Both submission is supposed to be TLE as they are both $$$O(n^3)$$$.