链接：https://leetcode-cn.com/problems/max-area-of-island/
代码：
class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { int dp[55][55]; // dp(i,j) represent max from dp(0,0) to dp(i,j) int m = grid.size(); if(m == 0) return 0; int n = grid[0].size(); if(n == 0) return 0; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 && j == 0) { dp[0][0] = grid[0][0]; } else if(i == 0 && j != 0) { if(grid[0][j-1] == 1) { dp[i][j] = dp[i][j-1] + grid[i][j]; } else { dp[i][j] = max(grid[i][j], dp[i][j-1]); } } else if(j == 0 && i != 0) { if(grid[i-1][0] == 1) { dp[i][j] = dp[i-1][j] + grid[i][j]; } else { dp[i][j] = max(grid[i][j], dp[i-1][j]); } } else { // int left = 0; // if(grid[i][j-1] == 1) { // left = dp[i][j-1] + grid[i][j]; // } // else { // left = max(grid[i][j], dp[i][j-1]); // } // int up = 0; // if(grid[i-1][j] == 1) { // up = dp[i-1][j] + grid[i][j]; // } // else { // up = max(grid[i][j], dp[i-1][j]); // } // dp[i][j] = left + up - dp[i-1][j-1]; if(grid[i][j] == 0) { dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]; } else { if(grid[i][j-1] == 1 && grid[i-1][j] == 1) { dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + 1; } else if(grid[i][j-1] == 1 && grid[i-1][j] != 1) { dp[i][j] = max(dp[i][j-1]+1, dp[i-1][j]); } else if(grid[i][j-1] != 1 && grid[i-1][j] == 1) { dp[i][j] = max(dp[i-1][j]+1, dp[i][j-1]); } else { dp[i][j] = max(dp[i-1][j-1], 1); } } } } } for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { cout << dp[i][j] << " "; } cout << endl; } return dp[m-1][n-1]; } };
class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { int dp[55][55]; // dp(i,j) represent max from dp(0,0) to dp(i,j) int m = grid.size(); if(m == 0) return 0; int n = grid[0].size(); if(n == 0) return 0; int res = 0; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 && j == 0) { dp[0][0] = grid[0][0]; res = max(res, dp[i][j]); } else if(i == 0 && j != 0) { if(grid[0][j-1] == 1 && grid[0][j] == 1) { dp[i][j] = dp[i][j-1] + 1; res = max(res, dp[i][j]); } else { if(grid[i][j] == 1) dp[i][j] = 1, res = max(res, dp[i][j]); else dp[i][j] = 0; } } else if(j == 0 && i != 0) { if(grid[i-1][0] == 1 && grid[i][0] == 1) { dp[i][j] = dp[i-1][j] + 1; res = max(res, dp[i][j]); } else { if(grid[i][j] == 1) dp[i][j] = 1, res = max(res, dp[i][j]); else dp[i][j] = 0; } } else { if(grid[i][j] == 0) {dp[i][j] = 0; continue;} if(grid[i][j-1] == 1 && grid[i-1][j] == 1) { dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + 1; res = max(res, dp[i][j]); } else if(grid[i][j-1] == 1 && grid[i-1][j] == 0) { dp[i][j] = dp[i][j-1]+1; res = max(res, dp[i][j]); } else if(grid[i][j-1] == 0 && grid[i-1][j] == 1) { dp[i][j] = dp[i-1][j]+1; res = max(res, dp[i][j]); } else { dp[i][j] = 1; res = max(res, dp[i][j]); } } } } for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { cout << dp[i][j] << " "; } cout << endl; } return res; } };
class Solution { public: int vis[55][55]; int res = 0; int graph[1000]; int cnt = 0; int is_valid(int i, int j, vector<vector<int>>& grid) { // cout << "+++++" << endl; int m = grid.size(); int n = grid[0].size(); if(i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1) return 1; else return 0; } void dfs(int i, int j, vector<vector<int>>& grid) { // cout << "=====" << endl; graph[cnt]++; if(vis[i][j] == 1) return; vis[i][j] = 1; res = max(res, graph[cnt]); // cout << res << endl; if(is_valid(i-1, j, grid) && !vis[i-1][j]) { dfs(i-1, j, grid); } if(is_valid(i+1, j, grid) && !vis[i+1][j]) { dfs(i+1, j, grid); } if(is_valid(i, j-1, grid) && !vis[i][j-1]) { dfs(i, j-1, grid); } if(is_valid(i, j+1, grid) && !vis[i][j+1]) { dfs(i, j+1, grid); } } int maxAreaOfIsland(vector<vector<int>>& grid) { int m = grid.size(); if(m == 0) { return 0; } int n = grid[0].size(); if(n == 0) { return 0; } // debug // for(int i = 0; i < m; i++) { // for(int j = 0; j < n; j++) { // cout << vis[i][j] << " "; // } // cout << endl; // } for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { // is it necessary? if(!vis[i][j] && grid[i][j] == 1) { dfs(i, j, grid); cnt++; } } } // debug // for(int i = 0; i < m; i++) { // for(int j = 0; j < n; j++) { // cout << vis[i][j] << " "; // } // cout << endl; // } return res; } };
class Solution { public: int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) { int m = grid.size(); int n = grid[0].size(); if(cur_i<0 || cur_j<0 || cur_i>=m || cur_j>=n || grid[cur_i][cur_j]==0) return 0; grid[cur_i][cur_j] = 0; int dx[5] = {-1, 0, 1, 0}; int dy[5] = {0, -1, 0, 1}; int ans = 1; for(int i = 0; i < 4; i++) { int next_i = cur_i + dx[i]; int next_j = cur_j + dy[i]; ans += dfs(grid, next_i, next_j); } return ans; } int maxAreaOfIsland(vector<vector<int>>& grid) { int ans = 0; int m = grid.size(); if(m == 0) return 0; int n = grid[0].size(); if(n == 0) return 0; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { ans = max(ans, dfs(grid, i, j)); } } return ans; } };
思路：dp 都是错的，version1 的代码设dp(i,j)是以 i，j 为右下角的矩形最大值，由于不满足最优子结构，没办法写转移方程。
version2 的代码设 dp(i,j)是以 i，j 为右下角的连通的矩形最大值，状态转移方程是可以写出来，但本身这个状态就设计有问题，不能求出最优解（面对 T 字形不能）。
dfs 都是对的，version1 自己写得很麻烦，矩阵没有传引用导致 TLE，代码也不好看，尽量使递归方程带有意义。
version2 的代码是看的题解，很优雅，很漂亮。
原文：https://www.cnblogs.com/FriskyPuppy/p/12920380.html
