DP solution with explanation


  • 0
    C

    The idea is simple:

    Use another matrix to store the area information.
    f[i][j] refers to the area which relay on the right-button corner of the matrix

    So that, if matrix[i][j] == '0', f[i][j] will be 0;

    else
    f[i][j] will rely on its up, left and up-left value in f.

    The relationship is

                        if(f[i-1][j]>=f[i-1][j-1] && f[i][j-1]>=f[i-1][j-1])
                            f[i][j] = (int)pow(sqrt(f[i-1][j-1])+1,2);
                        else{
                            int up = sqrt(f[i-1][j]);
    	              	    int left = sqrt(f[i][j-1]);
    	              	    int final = min(up,left);
                            f[i][j] = (int)pow(final+1,2);
                        }
    

    That is the basic algorithm of this DP solution


Log in to reply
 

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