Блог пользователя StellarSpecter

Автор StellarSpecter, история, 4 месяца назад, По-английски

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!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

9q3418

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Both submission is supposed to be TLE as they are both $$$O(n^3)$$$.