Can there be a DP solution for this one?


  • 0
    I was trying to figure out a DP solution for this one. For example, use the DP matrix to record the area of the island we accessed.
    I thought the point here is trying to find out if the current land we just accessed could somehow be connected to an existed island. If so, we added this piece of new land to the existed island. Otherwise, it is an island of its own.
    We know if we are connected to any existed island. If we are at position (i,j) and grid[i, j] = 1, then it is easy for us to see if the current land is connected to one of its adjacent lands(grid[i-1, j] = 1 or grid[i, j+1] = 1) or if it connects both of its adjacent lands with itself to form an new island (grid[i-1, j] = 1, grid[i, j+1] = 1, grid[i, j] = 1) . we can easily express that in DP matrix. However, when grid[i, j] = 0, while we know we can't add it to any island, there is still a possibility that grid[i-1, j] = 1 and grid[i, j+1] = 1 and they are connected somehow, just NOT by grid[i, j]. (Think about a circle with a break at point [i, j]). Then in this case how do we populate DP[i, j], should we assign DP[i,j] = DP[i - 1, j] + DP[i, j - 1] - DP[i - 1, j - 1] if they are connected. Or DP[i,j] = Math.Max(DP[i - 1, j], DP[i, j - 1]) if they are not connected. 
    I'm sure someone has already gone through this thinking process. If it is not feasible, what was the reason behind scene?

Log in to reply
 

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