Why this DP method can't work? Help!


  • 0
    S
    	int  ** matric;
    	matric = new int * [s.length()];
    	for (int j = 0; j<s.length(); j++)
    	{
    		matric[j] = new int [s.length()]; 
    	}
    
    	int length = s.length();
    	for (int i = 0; i < length; ++i)
    	{
    		matric[i][i] = 1;
    
    	}
    	for (int i = 0, j = 1; j < length; ++i, ++j)
    	{
    		if (s[i] == s[j])
    		{
    			matric[i][j] = 1;
    		}
    	}
    
    	for (int k = 0; k < length - 2; ++k)
    	{
    		for (int i = 0,  j = k + 2; i < length&&j < length; ++i, ++j)
    		{
    			if (matric[i + 1][j - 1] == 1 && s[i] == s[j])
    			{
    				matric[i][j] = 1;
    			}
    			else
    			{
    				matric[i][j] = 0;
    			}
    		}
    	}
    	pair<int, int > result(0, 0);
    	for (int i = 0; i < length; ++i)
    	{
    		for (int j = i; j < length; ++j)
    		{
    			if (matric[i][j] == 1 && j - i > result.second - result.first)
    			{
    				result.first = i;
    				result.second = j;
    			}
    		}
    	}
    	for (int i = 0; i<s.length(); i++)
    	{
    		delete[] matric[i]; 
    	}
    	delete[] matric;
    	return s.substr(result.first, result.second - result.first + 1);

Log in to reply
 

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