给定一个二维的 0-1 矩阵，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。





Input:

[[1,0,1,1,0,1,0,1],

[1,0,1,1,0,1,1,1],

[0,0,0,0,0,0,0,1]]

Output: 6


思路：

有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这种做法叫做状态记录或记忆化（memoization）。

一般来说，深度优先搜索类型的题可以分为主函数和辅函数，主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。辅函数则负责深度优先搜索的递归调用。当然，我们也可以使用栈（stack）实现深度优先搜索，但因为栈与递归的调用原理相同，而递归相对便于实现，因此刷题时笔者推荐使用递归式写法，同时也方便进行回溯（见下节）。不过在实际工程上，直接使用栈可能才是最好的选择，一是因为便于理解，二是更不易出现递归栈满的情况。我们先展示使用栈的写法：

（1）遍历所有元素

（2）遇到1的直接入栈计算，栈里面所有元素在四个方向有1的继续入栈

（3）标记好已经搜索过的地方

```python
def maxAreaOfIsland(grid):
    direction = [-1, 0, 1, 0, -1]
    m = len(grid)  # 行
    n = len(grid[0]) if m else 0  # 列
    area = 0
    for i in range(0, m):
        for j in range(0, n): # （1）遍历所有元素
            if grid[i][j]:  # 首先得确认这是一块陆地，才能往下发展
                local_area = 1
                grid[i][j] = 0
                island = []
                island.append([i, j])
                while len(island): # 遇到1的直接入栈计算，栈里面所有元素在四个方向有1的继续入栈
                    r, c = island.pop()  # 栈顶元素
                    for k in range(0, 4):  # 栈顶元素的四个方向
                        x = r + direction[k]
                        y = c + direction[k + 1]
                        if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == 1:  # 栈顶元素的这个方向遇到的是不是1
                            grid[x][y] = 0
                            local_area += 1
                            island.append([x, y])
                area = max(area, local_area)
    return area
grid_t = [[1, 0, 1, 1, 0, 1, 0, 1],
          [1, 0, 1, 1, 0, 1, 1, 1],
          [0, 0, 0, 0, 0, 0, 0, 1]]
print(maxAreaOfIsland(grid_t))
```

在辅函数里，一个一定要注意的点是辅函数内递归搜索时，边界条件的判定。边界判定一般

有两种写法，一种是先判定是否越界，只有在合法的情况下才进行下一步搜索（即判断放在调用

递归函数前）；另一种是不管三七二十一先进行下一步搜索，待下一步搜索开始时再判断是否合

法（即判断放在辅函数第一行）。

此外的主函数+辅助函数的写法（C++）:

```c
vector<int> direction { -1, 0, 1, 0, -1 };
/* 主函数 */
int maxAreaOfIsland( vector<vector<int> > & grid )
{
 if ( grid.empty() || grid[0].empty() )
  return(0);
 int max_area = 0;
 for ( int i = 0; i < grid.size(); ++i )
 {
  for ( int j = 0; j < grid[0].size(); ++j )
  {
   if ( grid[i][j] == 1 )
   {
    max_area = max( max_area, dfs( grid, i, j ) );
   }
  }
 }
 return(max_area);
}
/* 辅函数 */
int dfs( vector<vector<int> > & grid, int r, int c )
{
 if ( grid[r][c] == 0 )
  return(0);
 grid[r][c] = 0;
 int x, y, area = 1;
 for ( int i = 0; i < 4; ++i )
 {
  x = r + direction[i], y = c + direction[i + 1];
  if ( x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() )
  {
   area += dfs( grid, x, y );
  }
 }
 return(area);
}
```


```c
/* 主函数 */
int maxAreaOfIsland( vector<vector<int> > & grid )
{
 if ( grid.empty() || grid[0].empty() )
  return(0);
 int max_area = 0;
 for ( int i = 0; i < grid.size(); ++i )
 {
  for ( int j = 0; j < grid[0].size(); ++j )
  {
   max_area = max( max_area, dfs( grid, i, j ) );
  }
 }
 return(max_area);
}
/* 辅函数 */
int dfs( vector<vector<int> > & grid, int r, int c )
{
 if ( r < 0 || r >= grid.size() ||
      c < 0 || c >= grid[0].size() || grid[r][c] == 0 )
 {
  return(0);
 }
 grid[r][c] = 0;
 return(1 + dfs( grid, r + 1, c ) + dfs( grid, r - 1, c ) +
        dfs( grid, r, c + 1 ) + dfs( grid, r, c - 1 ) );
}
```

参考：LeetCode 101：和你一起你轻松刷题（C++）

【算法题目】【DFS】岛屿的最大面积

https://zhuanlan.zhihu.com/p/68358814





![在这里插入图片描述](/static/img/images/00464.png)

抛硬币多少次才连续两次正面朝上

[https://zhuanlan.zhihu.com/p/96229700](https://zhuanlan.zhihu.com/p/96229700)

匈牙利算法 二分图匹配 求二分图的最大匹配数和最小点覆盖数

![在这里插入图片描述](/static/img/images/00956.png)





[https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/](https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/)

作者：nettee

链接：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

动态规划的的四个解题步骤是：

1 定义子问题

![在这里插入图片描述](/static/img/images/00957.png)

2 写出子问题的递推关系

![在这里插入图片描述](/static/img/images/00958.png)

![在这里插入图片描述](/static/img/images/00959.png)


3 确定 DP 数组的计算顺序

![在这里插入图片描述](/static/img/images/00960.png)

![在这里插入图片描述](/static/img/images/00961.png)

```python
def rob(self, nums: List[int]) -> int:
    if len(nums) == 0:
        return 0
    # 子问题：
    # f(k) = 偷 [0..k) 房间中的最大金额
    # f(0) = 0
    # f(1) = nums[0]
    # f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
    N = len(nums)
    dp = [0] * (N+1)
    dp[0] = 0
    dp[1] = nums[0]
    for k in range(2, N+1):
        dp[k] = max(dp[k-1], nums[k-1] + dp[k-2])
    return dp[N]
作者：nettee
链接：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

4 空间优化（可选）

![在这里插入图片描述](/static/img/images/00962.png)

![在这里插入图片描述](/static/img/images/00963.gif)



```python
def rob(self, nums: List[int]) -> int:
    prev = 0
    curr = 0
    # 每次循环，计算“偷到当前房子为止的最大金额”
    for i in nums:
        # 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
        # dp[k] = max{ dp[k-1], dp[k-2] + i }
        prev, curr = curr, max(curr, prev + i)
        # 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
    return curr
作者：nettee
链接：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

198. 打家劫舍 【动态规划】 好文分享

先序遍历和后序遍历为什么不能唯一地确定一棵树？：





[https://blog.csdn.net/GYQJN/article/details/52709912](https://blog.csdn.net/GYQJN/article/details/52709912)

只有每个节点度为2或者0的时候前序和后序才能唯一确定一颗二叉树，只有一个子节点是无法确定的，因为你无法判断他是左子树还是右子树。

105. 从前序与中序遍历序列构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

106. 从中序与后序遍历序列构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

108. 根据前序和后序遍历构造二叉树

[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)



从来都是用来当填空题的。现在要求写程序。

比如：
```c
     A
  B     C
F      D  E
```

a=['A','B','F','C','D','E']   #前序样子

b=['F','B','A','D','C','E']   #中序样子

c=['F','B','D','E','C','A']  #后序样子

规律：

![在这里插入图片描述](/static/img/images/00964.png)

要点：树的前序遍历第一个是根节点。长度关系。子数递归满足此条件。


```python
from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def buildTreeFromPreorderInorder(self, preorder: List[str], inorder: List[str]) -> TreeNode:
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        def helper(preorder_left: int, preorder_right: int, inorder_left: int, inorder_right: int):
            if preorder_left > preorder_right:
                return None
            # 前序遍历中的第一个节点就是根节点
            preorder_root = preorder_left
            # 在中序遍历中定位根节点
            inorder_root = index[preorder[preorder_root]]
            # 先把根节点建立出来
            root = TreeNode(preorder[preorder_root])
            # 得到左子树中的节点数目
            size_left_subtree = inorder_root - inorder_left
            # 递归地构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = helper(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = helper(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
            return root
        return helper(0, n - 1, 0, n - 1)
    def buildTreeFromInorderPostorder(self, inorder , postorder):
        temp=postorder[:]
        def helper(in_left, in_right):
            # 如果这里没有节点构造二叉树了，就结束
            if in_left > in_right:
                return None
            # 选择 post_idx 位置的元素作为当前子树根节点
            val = temp.pop()
            root = TreeNode(val)
            # 根据 root 所在位置分成左右两棵子树
            index = idx_map[val]
            # 构造右子树
            root.right = helper(index + 1, in_right)
            # 构造左子树
            root.left = helper(in_left, index - 1)
            return root
        # 建立（元素，下标）键值对的哈希表
        idx_map = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(inorder) - 1)
    def constructFromPreorderPostorder(self, pre, post):
        if not pre:
            return None
        node = TreeNode(pre[0])
        if len(pre) == 1:
            return node
        i = post.index(pre[1])
        node.left = self.constructFromPreorderPostorder(pre[1:i + 2], post[:i + 1])
        node.right = self.constructFromPreorderPostorder(pre[i + 2:], post[i + 1:-1])
        return node
    def preorderTraversal(self, root: TreeNode) -> List[str]:
        def preorder(root: TreeNode):
            if not root:
                return
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)
        res = list()
        preorder(root)
        return res
    def inorderTraversal(self, root: TreeNode) -> List[str]:
        def preorder(root: TreeNode):
            if not root:
                return
            preorder(root.left)
            res.append(root.val)
            preorder(root.right)
        res = list()
        preorder(root)
        return res
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def postorder(root: TreeNode):
            if not root:
                return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        res = list()
        postorder(root)
        return res
a = ['A', 'B', 'F', 'C', 'D', 'E']  #前序样子
b = ['F', 'B', 'A', 'D', 'C', 'E']  #中序样子
c = ['F', 'B', 'D', 'E', 'C', 'A']  #后序样子
onexianxu=Solution().buildTreeFromInorderPostorder(b,c)
print('先序',Solution().preorderTraversal(onexianxu))
onezhong=Solution().constructFromPreorderPostorder(a, c)
print('中序',Solution().inorderTraversal(onezhong))
onehouxu=Solution().buildTreeFromPreorderInorder(a,b)
print('后序',Solution().postorderTraversal(onehouxu))
```