2d dp, scan every row to get the most left and most right, scan the whole mat to get the most height