给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

 

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = [["0"]]
输出：0

示例 3：

输入：matrix = [["1"]]
输出：1

 

提示：

• rows == matrix.length
• cols == matrix[0].length
• 1 <= rows, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

回顾一下，这是 84. 柱状图中最大的矩形 的图：

{:width=400}

对于本题，设 $\textit{matrix}$ 有 $m$ 行，我们可以枚举矩形的底边，做 $m$ 次 84 题。

{:width=300}

• 以第一行为底的柱子高度为 $[1,0,1,0,0]$，最大矩形面积为 $1$。
• 以第二行为底的柱子高度为 $[2,0,2,1,1]$，最大矩形面积为 $3$。
• 以第三行为底的柱子高度为 $[3,1,3,2,2]$，最大矩形面积为 $6$。
• 以第四行为底的柱子高度为 $[4,0,0,3,0]$，最大矩形面积为 $4$。
• 答案为 $\max(1,3,6,4) = 6$。

由于我们枚举的是矩形的底边，如果 $\textit{matrix}[i][j]=0$，那么没有柱子，高度等于 $0$。否则，在上一行柱子的基础上，把柱子高度增加 $1$。形象地说，就是在柱子下面垫一块石头，把柱子抬高。

###py

class Solution:
    # 84. 柱状图中最大的矩形
    def largestRectangleArea(self, heights: List[int]) -> int:
        st = [-1]  # 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        ans = 0
        for right, h in enumerate(heights):
            while len(st) > 1 and heights[st[-1]] >= h:
                i = st.pop()  # 矩形的高（的下标）
                left = st[-1]  # 栈顶下面那个数就是 left
                ans = max(ans, heights[i] * (right - left - 1))
            st.append(right)
        return ans

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        n = len(matrix[0])
        heights = [0] * (n + 1)  # 末尾多一个 0，理由见我 84 题题解
        ans = 0
        for row in matrix:
            # 计算底边为 row 的柱子高度
            for j, c in enumerate(row):
                if c == '0':
                    heights[j] = 0  # 柱子高度为 0
                else:
                    heights[j] += 1  # 柱子高度加一
            ans = max(ans, self.largestRectangleArea(heights))  # 调用 84 题代码
        return ans

###java

class Solution {
    int maximalRectangle(char[][] matrix) {
        int n = matrix[0].length;
        int[] heights = new int[n + 1]; // 末尾多一个 0，理由见我 84 题题解
        int ans = 0;
        for (char[] row : matrix) {
            // 计算底边为 row 的柱子高度
            for (int j = 0; j < n; j++) {
                if (row[j] == '0') {
                    heights[j] = 0; // 柱子高度为 0
                } else {
                    heights[j]++; // 柱子高度加一
                }
            }
            ans = Math.max(ans, largestRectangleArea(heights)); // 调用 84 题代码
        }
        return ans;
    }

    // 84. 柱状图中最大的矩形
    private int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] st = new int[n]; // 用数组模拟栈
        int top = -1; // 栈顶下标
        st[++top] = -1; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        int ans = 0;
        for (int right = 0; right < n; right++) {
            int h = heights[right];
            while (top > 0 && heights[st[top]] >= h) {
                int i = st[top--]; // 矩形的高（的下标）
                int left = st[top]; // 栈顶下面那个数就是 left
                ans = Math.max(ans, heights[i] * (right - left - 1));
            }
            st[++top] = right;
        }
        return ans;
    }
}

###cpp

class Solution {
    // 84. 柱状图中最大的矩形
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        st.push(-1); // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        int ans = 0;
        for (int right = 0; right < heights.size(); right++) {
            int h = heights[right];
            while (st.size() > 1 && heights[st.top()] >= h) {
                int i = st.top(); // 矩形的高（的下标）
                st.pop();
                int left = st.top(); // 栈顶下面那个数就是 left
                ans = max(ans, heights[i] * (right - left - 1));
            }
            st.push(right);
        }
        return ans;
    }

public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix[0].size();
        vector<int> heights(n + 1); // 末尾多一个 0，理由见我 84 题题解
        int ans = 0;
        for (auto& row : matrix) {
            // 计算底边为 row 的柱子高度
            for (int j = 0; j < n; j++) {
                if (row[j] == '0') {
                    heights[j] = 0; // 柱子高度为 0
                } else {
                    heights[j]++; // 柱子高度加一
                }
            }
            ans = max(ans, largestRectangleArea(heights)); // 调用 84 题代码
        }
        return ans;
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

// 84. 柱状图中最大的矩形
int largestRectangleArea(int* heights, int n) {
    int* stack = malloc(n * sizeof(int));
    int top = -1; // 栈顶下标
    stack[++top] = -1; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
    int ans = 0;
    for (int right = 0; right < n; right++) {
        int h = heights[right];
        while (top > 0 && heights[stack[top]] >= h) {
            int i = stack[top--]; // 矩形的高（的下标）
            int left = stack[top]; // 栈顶下面那个数就是 left
            ans = MAX(ans, heights[i] * (right - left - 1));
        }
        stack[++top] = right;
    }
    free(stack);
    return ans;
}

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixColSize[0];
    int* heights = calloc(n + 1, sizeof(int)); // 末尾多一个 0，理由见我 84 题题解
    int ans = 0;
    for (int i = 0; i < matrixSize; i++) {
        char* row = matrix[i];
        // 计算底边为 row 的柱子高度
        for (int j = 0; j < n; j++) {
            if (row[j] == '0') {
                heights[j] = 0; // 柱子高度为 0
            } else {
                heights[j]++; // 柱子高度加一
            }
        }
        ans = MAX(ans, largestRectangleArea(heights, n + 1)); // 调用 84 题代码，注意传入的是 n+1
    }
    free(heights);
    return ans;
}

###go

// 84. 柱状图中最大的矩形
func largestRectangleArea(heights []int) (ans int) {
    st := []int{-1} // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
    for right, h := range heights {
        for len(st) > 1 && heights[st[len(st)-1]] >= h {
            i := st[len(st)-1] // 矩形的高（的下标）
            st = st[:len(st)-1]
            left := st[len(st)-1] // 栈顶下面那个数就是 left
            ans = max(ans, heights[i]*(right-left-1))
        }
        st = append(st, right)
    }
    return
}

func maximalRectangle(matrix [][]byte) (ans int) {
    heights := make([]int, len(matrix[0])+1) // 末尾多一个 0，理由见我 84 题题解
    for _, row := range matrix {
        // 计算底边为 row 的柱子高度
        for j, c := range row {
            if c == '0' {
                heights[j] = 0 // 柱子高度为 0
            } else {
                heights[j]++ // 柱子高度加一
            }
        }
        ans = max(ans, largestRectangleArea(heights)) // 调用 84 题代码
    }
    return
}

###js

// 84. 柱状图中最大的矩形
var largestRectangleArea = function(heights) {
    const st = [-1]; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
    let ans = 0;
    for (let right = 0; right < heights.length; right++) {
        const h = heights[right]
        while (st.length > 1 && heights[st[st.length - 1]] >= h) {
            const i = st.pop(); // 矩形的高（的下标）
            const left = st[st.length - 1]; // 栈顶下面那个数就是 left
            ans = Math.max(ans, heights[i] * (right - left - 1));
        }
        st.push(right);
    }
    return ans;
};

var maximalRectangle = function(matrix) {
    const n = matrix[0].length;
    let heights = Array(n + 1).fill(0); // 末尾多一个 0，理由见我 84 题题解
    let ans = 0;
    for (const row of matrix) {
        // 计算底边为 row 的柱子高度
        for (let j = 0; j < n; j++) {
            if (row[j] === '0') {
                heights[j] = 0; // 柱子高度为 0
            } else {
                heights[j]++; // 柱子高度加一
            }
        }
        ans = Math.max(ans, largestRectangleArea(heights)); // 调用 84 题代码
    }
    return ans;
};

###rust

impl Solution {
    // 84. 柱状图中最大的矩形
    fn largest_rectangle_area(heights: &[i32]) -> i32 {
        let mut st = vec![-1]; // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        let mut ans = 0;
        for (right, &h) in heights.iter().enumerate() {
            let right = right as i32;
            while st.len() > 1 && heights[*st.last().unwrap() as usize] >= h {
                let i = st.pop().unwrap() as usize; // 矩形的高（的下标）
                let left = *st.last().unwrap(); // 栈顶下面那个数就是 left
                ans = ans.max(heights[i] * (right - left - 1));
            }
            st.push(right);
        }
        ans
    }

    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let n = matrix[0].len();
        let mut heights = vec![0; n + 1]; // 末尾多一个 0，理由见我 84 题题解
        let mut ans = 0;
        for row in matrix {
            // 计算底边为 row 的柱子高度
            for (j, c) in row.into_iter().enumerate() {
                if c == '0' {
                    heights[j] = 0; // 柱子高度为 0
                } else {
                    heights[j] += 1; // 柱子高度加一
                }
            }
            ans = ans.max(Self::largest_rectangle_area(&heights)); // 调用 84 题代码
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(mn)$，其中 $m$ 和 $n$ 分别为 $\textit{matrix}$ 的行数和列数。做 $m$ 次 84 题，每次 $\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(n)$。

相似题目

见下面单调栈题单的「二、矩形」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

方法一: 使用柱状图的优化暴力方法

思路与算法

最原始地，我们可以列举每个可能的矩形。我们枚举矩形所有可能的左上角坐标和右下角坐标，并检查该矩形是否符合要求。然而该方法的时间复杂度过高，不能通过所有的测试用例，因此我们必须寻找其他方法。

我们首先计算出矩阵的每个元素的左边连续 $1$ 的数量，使用二维数组 $\textit{left}$ 记录，其中 $\textit{left}[i][j]$ 为矩阵第 $i$ 行第 $j$ 列元素的左边连续 $1$ 的数量。

<,,,,,,,,,>

随后，对于矩阵中任意一个点，我们枚举以该点为右下角的全 $1$ 矩形。

具体而言，当考察以 $\textit{matrix}[i][j]$ 为右下角的矩形时，我们枚举满足 $0 \le k \le i$ 的所有可能的 $k$，此时矩阵的最大宽度就为

$$
\textit{left}[i][j], \textit{left}[i-1][j], \ldots, \textit{left}[k][j]
$$

的最小值。

下图有助于理解。给定每个点的最大宽度，可计算出底端黄色方块的最大矩形面积。

<,,,,,,>

对每个点重复这一过程，就可以得到全局的最大矩形。

我们预计算最大宽度的方法事实上将输入转化成了一系列的柱状图，我们针对每个柱状图计算最大面积。

{:align="center"}

于是，上述方法本质上是「84. 柱状图中最大的矩形」题中优化暴力算法的复用。

代码

###C++

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].size();
        vector<vector<int>> left(m, vector<int>(n, 0));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = min(width, left[k][j]);
                    area = max(area, (i - k + 1) * width);
                }
                ret = max(ret, area);
            }
        }
        return ret;
    }
};

###Java

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, (i - k + 1) * width);
                }
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}

###JavaScript

var maximalRectangle = function(matrix) {
    const m = matrix.length;
    if (m === 0) {
        return 0;
    }
    const n = matrix[0].length;
    const left = new Array(m).fill(0).map(() => new Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                left[i][j] = (j === 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
    }

    let ret = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '0') {
                continue;
            }
            let width = left[i][j];
            let area = width;
            for (let k = i - 1; k >= 0; k--) {
                width = Math.min(width, left[k][j]);
                area = Math.max(area, (i - k + 1) * width);
            }
            ret = Math.max(ret, area);
        }
    }
    return ret;
};

###go

func maximalRectangle(matrix [][]byte) (ans int) {
    if len(matrix) == 0 {
        return
    }
    m, n := len(matrix), len(matrix[0])
    left := make([][]int, m)
    for i, row := range matrix {
        left[i] = make([]int, n)
        for j, v := range row {
            if v == '0' {
                continue
            }
            if j == 0 {
                left[i][j] = 1
            } else {
                left[i][j] = left[i][j-1] + 1
            }
        }
    }
    for i, row := range matrix {
        for j, v := range row {
            if v == '0' {
                continue
            }
            width := left[i][j]
            area := width
            for k := i - 1; k >= 0; k-- {
                width = min(width, left[k][j])
                area = max(area, (i-k+1)*width)
            }
            ans = max(ans, area)
        }
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

###C

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    if (m == 0) {
        return 0;
    }
    int n = matrixColSize[0];
    int left[m][n];
    memset(left, 0, sizeof(left));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
    }

    int ret = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '0') {
                continue;
            }
            int width = left[i][j];
            int area = width;
            for (int k = i - 1; k >= 0; k--) {
                width = fmin(width, left[k][j]);
                area = fmax(area, (i - k + 1) * width);
            }
            ret = fmax(ret, area);
        }
    }
    return ret;
}

###C#

public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        int m = matrix.Length;
        if (m == 0) return 0;
        int n = matrix[0].Length;
        int[][] left = new int[m][];
        for (int i = 0; i < m; i++) {
            left[i] = new int[n];
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.Min(width, left[k][j]);
                    area = Math.Max(area, (i - k + 1) * width);
                }
                ret = Math.Max(ret, area);
            }
        }
        return ret;
    }
}

###Python

class Solution:
    def maximalRectangle(self, matrix: list[list[str]]) -> int:
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        left = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    left[i][j] = (0 if j == 0 else left[i][j - 1]) + 1

        ret = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '0':
                    continue
                width = left[i][j]
                area = width
                for k in range(i - 1, -1, -1):
                    width = min(width, left[k][j])
                    area = max(area, (i - k + 1) * width)
                ret = max(ret, area)
        return ret

###TypeScript

function maximalRectangle(matrix: string[][]): number {
    const m = matrix.length;
    if (m === 0) {
        return 0;
    }
    const n = matrix[0].length;
    const left: number[][] = Array.from({ length: m }, () => Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                left[i][j] = (j === 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
    }

    let ret = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '0') {
                continue;
            }
            let width = left[i][j];
            let area = width;
            for (let k = i - 1; k >= 0; k--) {
                width = Math.min(width, left[k][j]);
                area = Math.max(area, (i - k + 1) * width);
            }
            ret = Math.max(ret, area);
        }
    }
    return ret;
}

###Rust

impl Solution {
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let m = matrix.len();
        if m == 0 {
            return 0;
        }
        let n = matrix[0].len();
        let mut left = vec![vec![0; n]; m];

        for i in 0..m {
            for j in 0..n {
                if matrix[i][j] == '1' {
                    left[i][j] = if j == 0 { 0 } else { left[i][j - 1] } + 1;
                }
            }
        }

        let mut ret = 0;
        for i in 0..m {
            for j in 0..n {
                if matrix[i][j] == '0' {
                    continue;
                }
                let mut width = left[i][j];
                let mut area = width;
                for k in (0..i).rev() {
                    width = width.min(left[k][j]);
                    area = area.max((i - k + 1) * width);
                }
                ret = ret.max(area);
            }
        }
        ret as i32
    }
}

复杂度分析

• 时间复杂度：$O(m^2n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。计算 $\textit{left}$ 矩阵需要 $O(mn)$ 的时间。随后对于矩阵的每个点，需要 $O(m)$ 的时间枚举高度。故总的时间复杂度为 $O(mn) + O(mn) \cdot O(m) = O(m^2n)$。

• 空间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组，用于存储每个元素的左边连续 $1$ 的数量。

方法二：单调栈

思路与算法

在方法一中，我们讨论了将输入拆分成一系列的柱状图。为了计算矩形的最大面积，我们只需要计算每个柱状图中的最大面积，并找到全局最大值。

我们可以使用「84. 柱状图中最大的矩形的官方题解」中的单调栈的做法，将其应用在我们生成的柱状图中。

代码

###C++

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].size();
        vector<vector<int>> left(m, vector<int>(n, 0));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
            vector<int> up(m, 0), down(m, 0);

            stack<int> stk;
            for (int i = 0; i < m; i++) {
                while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
                    stk.pop();
                }
                up[i] = stk.empty() ? -1 : stk.top();
                stk.push(i);
            }
            stk = stack<int>();
            for (int i = m - 1; i >= 0; i--) {
                while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
                    stk.pop();
                }
                down[i] = stk.empty() ? m : stk.top();
                stk.push(i);
            }

            for (int i = 0; i < m; i++) {
                int height = down[i] - up[i] - 1;
                int area = height * left[i][j];
                ret = max(ret, area);
            }
        }
        return ret;
    }
};

###Java

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        int[][] left = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
            int[] up = new int[m];
            int[] down = new int[m];

            Deque<Integer> stack = new ArrayDeque<Integer>();
            for (int i = 0; i < m; i++) {
                while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
                    stack.pop();
                }
                up[i] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(i);
            }
            stack.clear();
            for (int i = m - 1; i >= 0; i--) {
                while (!stack.isEmpty() && left[stack.peek()][j] >= left[i][j]) {
                    stack.pop();
                }
                down[i] = stack.isEmpty() ? m : stack.peek();
                stack.push(i);
            }

            for (int i = 0; i < m; i++) {
                int height = down[i] - up[i] - 1;
                int area = height * left[i][j];
                ret = Math.max(ret, area);
            }
        }
        return ret;
    }
}

###JavaScript

var maximalRectangle = function(matrix) {
    const m = matrix.length;
    if (m === 0) {
        return 0;
    }
    const n = matrix[0].length;
    const left = new Array(m).fill(0).map(() => new Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                left[i][j] = (j === 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
    }

    let ret = 0;
    for (let j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
        const up = new Array(m).fill(0);
        const down = new Array(m).fill(0);

        let stack = new Array();
        for (let i = 0; i < m; i++) {
            while (stack.length && left[stack[stack.length - 1]][j] >= left[i][j]) {
                stack.pop();
            }
            up[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
            stack.push(i);
        }
        stack = [];
        for (let i = m - 1; i >= 0; i--) {
            while (stack.length && left[stack[stack.length - 1]][j] >= left[i][j]) {
                stack.pop();
            }
            down[i] = stack.length === 0 ? m : stack[stack.length - 1];
            stack.push(i);
        }

        for (let i = 0; i < m; i++) {
            const height = down[i] - up[i] - 1;
            const area = height * left[i][j];
            ret = Math.max(ret, area);
        }
    }
    return ret;
};

###go

func maximalRectangle(matrix [][]byte) (ans int) {
    if len(matrix) == 0 {
        return
    }
    m, n := len(matrix), len(matrix[0])
    left := make([][]int, m)
    for i, row := range matrix {
        left[i] = make([]int, n)
        for j, v := range row {
            if v == '0' {
                continue
            }
            if j == 0 {
                left[i][j] = 1
            } else {
                left[i][j] = left[i][j-1] + 1
            }
        }
    }
    for j := 0; j < n; j++ { // 对于每一列，使用基于柱状图的方法
        up := make([]int, m)
        down := make([]int, m)
        stk := []int{}
        for i, l := range left {
            for len(stk) > 0 && left[stk[len(stk)-1]][j] >= l[j] {
                stk = stk[:len(stk)-1]
            }
            up[i] = -1
            if len(stk) > 0 {
                up[i] = stk[len(stk)-1]
            }
            stk = append(stk, i)
        }
        stk = nil
        for i := m - 1; i >= 0; i-- {
            for len(stk) > 0 && left[stk[len(stk)-1]][j] >= left[i][j] {
                stk = stk[:len(stk)-1]
            }
            down[i] = m
            if len(stk) > 0 {
                down[i] = stk[len(stk)-1]
            }
            stk = append(stk, i)
        }
        for i, l := range left {
            height := down[i] - up[i] - 1
            area := height * l[j]
            ans = max(ans, area)
        }
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

###C

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;
    if (m == 0) {
        return 0;
    }
    int n = matrixColSize[0];
    int left[m][n];
    memset(left, 0, sizeof(left));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
    }

    int ret = 0;
    for (int j = 0; j < n; j++) {  // 对于每一列，使用基于柱状图的方法
        int up[m], down[m];
        memset(up, 0, sizeof(up));
        memset(down, 0, sizeof(down));
        int stk[m], top = 0;
        for (int i = 0; i < m; i++) {
            while (top > 0 && left[stk[top - 1]][j] >= left[i][j]) {
                top--;
            }
            up[i] = top == 0 ? -1 : stk[top - 1];
            stk[top++] = i;
        }
        top = 0;
        for (int i = m - 1; i >= 0; i--) {
            while (top > 0 && left[stk[top - 1]][j] >= left[i][j]) {
                top--;
            }
            down[i] = top == 0 ? m : stk[top - 1];
            stk[top++] = i;
        }

        for (int i = 0; i < m; i++) {
            int height = down[i] - up[i] - 1;
            int area = height * left[i][j];
            ret = fmax(ret, area);
        }
    }
    return ret;
}

###C#

public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        int m = matrix.Length;
        if (m == 0) return 0;
        int n = matrix[0].Length;
        int[][] left = new int[m][];
        for (int i = 0; i < m; i++) {
            left[i] = new int[n];
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }

        int ret = 0;
        for (int j = 0; j < n; j++) {
            int[] up = new int[m];
            int[] down = new int[m];
            Stack<int> stk = new Stack<int>();

            for (int i = 0; i < m; i++) {
                while (stk.Count > 0 && left[stk.Peek()][j] >= left[i][j])
                    stk.Pop();
                up[i] = stk.Count == 0 ? -1 : stk.Peek();
                stk.Push(i);
            }

            stk.Clear();
            for (int i = m - 1; i >= 0; i--) {
                while (stk.Count > 0 && left[stk.Peek()][j] >= left[i][j])
                    stk.Pop();
                down[i] = stk.Count == 0 ? m : stk.Peek();
                stk.Push(i);
            }

            for (int i = 0; i < m; i++) {
                int height = down[i] - up[i] - 1;
                ret = Math.Max(ret, height * left[i][j]);
            }
        }
        return ret;
    }
}

###Python

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        left = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    left[i][j] = (0 if j == 0 else left[i][j - 1]) + 1

        ret = 0
        for j in range(n):
            up = [0] * m
            down = [0] * m
            stk = []

            for i in range(m):
                while stk and left[stk[-1]][j] >= left[i][j]:
                    stk.pop()
                up[i] = stk[-1] if stk else -1
                stk.append(i)

            stk = []
            for i in range(m - 1, -1, -1):
                while stk and left[stk[-1]][j] >= left[i][j]:
                    stk.pop()
                down[i] = stk[-1] if stk else m
                stk.append(i)

            for i in range(m):
                height = down[i] - up[i] - 1
                ret = max(ret, height * left[i][j])

        return ret

###TypeScript

function maximalRectangle(matrix: string[][]): number {
    const m = matrix.length;
    if (m === 0) {
        return 0;
    }
    const n = matrix[0].length;
    const left: number[][] = Array.from({ length: m }, () => Array(n).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === '1') {
                left[i][j] = (j === 0 ? 0 : left[i][j - 1]) + 1;
            }
        }
    }

    let ret = 0;
    for (let j = 0; j < n; j++) {
        const up: number[] = new Array(m);
        const down: number[] = new Array(m);
        const stk: number[] = [];

        for (let i = 0; i < m; i++) {
            while (stk.length && left[stk[stk.length - 1]][j] >= left[i][j]) {
                stk.pop();
            }
            up[i] = stk.length ? stk[stk.length - 1] : -1;
            stk.push(i);
        }

        stk.length = 0;
        for (let i = m - 1; i >= 0; i--) {
            while (stk.length && left[stk[stk.length - 1]][j] >= left[i][j]) {
                stk.pop();
            }
            down[i] = stk.length ? stk[stk.length - 1] : m;
            stk.push(i);
        }

        for (let i = 0; i < m; i++) {
            const height = down[i] - up[i] - 1;
            ret = Math.max(ret, height * left[i][j]);
        }
    }

    return ret;
}

###Rust

impl Solution {
    pub fn maximal_rectangle(matrix: Vec<Vec<char>>) -> i32 {
        let m = matrix.len();
        if m == 0 {
            return 0;
        }
        let n = matrix[0].len();
        let mut left = vec![vec![0; n]; m];

        for i in 0..m {
            for j in 0..n {
                if matrix[i][j] == '1' {
                    left[i][j] = if j == 0 { 0 } else { left[i][j - 1] } + 1;
                }
            }
        }

        let mut ret = 0;
        for j in 0..n {
            let mut up = vec![0; m];
            let mut down = vec![0; m];
            let mut stk: Vec<usize> = Vec::new();

            for i in 0..m {
                while let Some(&top) = stk.last() {
                    if left[top][j] >= left[i][j] {
                        stk.pop();
                    } else {
                        break;
                    }
                }
                up[i] = stk.last().map(|&x| x as i32).unwrap_or(-1);
                stk.push(i);
            }

            stk.clear();
            for i in (0..m).rev() {
                while let Some(&top) = stk.last() {
                    if left[top][j] >= left[i][j] {
                        stk.pop();
                    } else {
                        break;
                    }
                }
                down[i] = stk.last().copied().unwrap_or(m);
                stk.push(i);
            }

            for i in 0..m {
                let height = down[i] - up[i] as usize - 1;
                ret = ret.max(height * left[i][j]);
            }
        }

        ret as i32
    }
}

读者可以自行比对上面的代码与此前第 84 题的代码的相似之处。

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。计算 $\textit{left}$ 矩阵需要 $O(mn)$ 的时间；对每一列应用柱状图算法需要 $O(m)$ 的时间，一共需要 $O(mn)$ 的时间。

• 空间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。我们分配了一个与给定矩阵等大的数组，用于存储每个元素的左边连续 $1$ 的数量。

题目描述（困难难度）

给一个只有 0 和 1 的矩阵，输出一个最大的矩形的面积，这个矩形里边只含有 1。

解法一 暴力破解

遍历每个点，求以这个点为矩阵右下角的所有矩阵面积。如下图的两个例子，橙色是当前遍历的点，然后虚线框圈出的矩阵是其中一个矩阵。

怎么找出这样的矩阵呢？如下图，如果我们知道了以这个点结尾的连续 1 的个数的话，问题就变得简单了。

1. 首先求出高度是 1 的矩形面积，也就是它自身的数，如图中橙色的 4，面积就是 4。

2. 然后向上扩展一行，高度增加一，选出当前列最小的数字，作为矩阵的宽，求出面积，对应上图的矩形框。

3. 然后继续向上扩展，重复步骤 2。

按照上边的方法，遍历所有的点，求出所有的矩阵就可以了。

以橙色的点为右下角，高度为 1。

高度为 2。

高度为 3。

###java

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    //保存以当前数字结尾的连续 1 的个数
    int[][] width = new int[matrix.length][matrix[0].length];
    int maxArea = 0;
    //遍历每一行
    for (int row = 0; row < matrix.length; row++) {
        for (int col = 0; col < matrix[0].length; col++) {
            //更新 width
            if (matrix[row][col] == '1') {
                if (col == 0) {
                    width[row][col] = 1;
                } else {
                    width[row][col] = width[row][col - 1] + 1;
                }
            } else {
                width[row][col] = 0;
            }
            //记录所有行中最小的数
            int minWidth = width[row][col];
            //向上扩展行
            for (int up_row = row; up_row >= 0; up_row--) {
                int height = row - up_row + 1;
                //找最小的数作为矩阵的宽
                minWidth = Math.min(minWidth, width[up_row][col]);
                //更新面积
                maxArea = Math.max(maxArea, height * minWidth);
            }
        }
    }
    return maxArea;
}

时间复杂度：O（m²n）。

空间复杂度：O（mn）。

解法二

接下来的解法，会让这道题变得异常简单。还记得84 题吗？求一个直方图矩形的最大面积。

大家可以先做84 题，然后回来考虑这道题。

再想一下这个题，看下边的橙色的部分，这完全就是上一道题呀！

算法有了，就是求出每一层的 heights[] 然后传给上一题的函数就可以了。

利用上一题的栈解法。

###java

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    int[] heights = new int[matrix[0].length];
    int maxArea = 0;
    for (int row = 0; row < matrix.length; row++) {
        //遍历每一列，更新高度
        for (int col = 0; col < matrix[0].length; col++) {
            if (matrix[row][col] == '1') {
                heights[col] += 1;
            } else {
                heights[col] = 0;
            }
        }
        //调用上一题的解法，更新函数
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;
}

public int largestRectangleArea(int[] heights) {
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    int p = 0;
    while (p < heights.length) {
        //栈空入栈
        if (stack.isEmpty()) {
            stack.push(p);
            p++;
        } else {
            int top = stack.peek();
            //当前高度大于栈顶，入栈
            if (heights[p] >= heights[top]) {
                stack.push(p);
                p++;
            } else {
                //保存栈顶高度
                int height = heights[stack.pop()];
                //左边第一个小于当前柱子的下标
                int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
                //右边第一个小于当前柱子的下标
                int RightLessMin = p;
                //计算面积
                int area = (RightLessMin - leftLessMin - 1) * height;
                maxArea = Math.max(area, maxArea);
            }
        }
    }
    while (!stack.isEmpty()) {
        //保存栈顶高度
        int height = heights[stack.pop()];
        //左边第一个小于当前柱子的下标
        int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
        //右边没有小于当前高度的柱子，所以赋值为数组的长度便于计算
        int RightLessMin = heights.length;
        int area = (RightLessMin - leftLessMin - 1) * height;
        maxArea = Math.max(area, maxArea);
    }
    return maxArea;
}

时间复杂度：O（mn）。

空间复杂度：O（n）。

利用上一题的解法四。

###java

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    int[] heights = new int[matrix[0].length];
    int maxArea = 0;
    for (int row = 0; row < matrix.length; row++) {
        //遍历每一列，更新高度
        for (int col = 0; col < matrix[0].length; col++) {
            if (matrix[row][col] == '1') {
                heights[col] += 1;
            } else {
                heights[col] = 0;
            }
        }
        //调用上一题的解法，更新函数
        maxArea = Math.max(maxArea, largestRectangleArea(heights));
    }
    return maxArea;
}

public int largestRectangleArea(int[] heights) {
    if (heights.length == 0) {
        return 0;
    }
    int[] leftLessMin = new int[heights.length];
    leftLessMin[0] = -1;
    for (int i = 1; i < heights.length; i++) {
        int l = i - 1;
        while (l >= 0 && heights[l] >= heights[i]) {
            l = leftLessMin[l];
        }
        leftLessMin[i] = l;
    }

    int[] rightLessMin = new int[heights.length];
    rightLessMin[heights.length - 1] = heights.length;
    for (int i = heights.length - 2; i >= 0; i--) {
        int r = i + 1;
        while (r <= heights.length - 1 && heights[r] >= heights[i]) {
            r = rightLessMin[r];
        }
        rightLessMin[i] = r;
    }
    int maxArea = 0;
    for (int i = 0; i < heights.length; i++) {
        int area = (rightLessMin[i] - leftLessMin[i] - 1) * heights[i];
        maxArea = Math.max(area, maxArea);
    }
    return maxArea;
}

时间复杂度：O（mn）。

空间复杂度：O（n）。

解法三

解法二中套用的栈的解法，我们其实可以不用调用函数，而是把栈糅合到原来求 heights 中。因为栈的话并不是一次性需要所有的高度，所以可以求出一个高度，然后就操作栈。

###java

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    int[] heights = new int[matrix[0].length + 1]; //小技巧后边讲
    int maxArea = 0;
    for (int row = 0; row < matrix.length; row++) {
        Stack<Integer> stack = new Stack<Integer>();
        heights[matrix[0].length] = 0;
        //每求一个高度就进行栈的操作
        for (int col = 0; col <= matrix[0].length; col++) {
            if (col < matrix[0].length) { //多申请了 1 个元素，所以要判断
                if (matrix[row][col] == '1') {
                    heights[col] += 1;
                } else {
                    heights[col] = 0;
                }
            }
            if (stack.isEmpty() || heights[col] >= heights[stack.peek()]) {
                stack.push(col);
            } else {
                //每次要判断新的栈顶是否高于当前元素
                while (!stack.isEmpty() && heights[col] < heights[stack.peek()]) {
                    int height = heights[stack.pop()];
                    int leftLessMin = stack.isEmpty() ? -1 : stack.peek();
                    int RightLessMin = col;
                    int area = (RightLessMin - leftLessMin - 1) * height;
                    maxArea = Math.max(area, maxArea);
                }
                stack.push(col);
            }
        }

    }
    return maxArea;
}

时间复杂度：O（mn）。

空间复杂度：O（n）。

里边有一个小技巧，84 题的栈解法中，我们用了两个 while 循环，第二个 while 循环用来解决遍历完元素栈不空的情况。其实，我们注意到两个 while 循环的逻辑完全一样的。所以我们可以通过一些操作，使得遍历结束后，依旧进第一个 while 循环，从而剩下了第 2 个 while 循环，代码看起来会更简洁。

那就是 heights 多申请一个元素，赋值为 0。这样最后一次遍历的时候，栈顶肯定会大于当前元素，所以就进入了第一个 while 循环。

解法四 动态规划

解法二中，用了 84 题的两个解法，解法三中我们把栈糅合进了原算法，那么另一种可以一样的思路吗？不行！因为栈不要求所有的高度，可以边更新，边处理。而另一种，是利用两个数组， leftLessMin [ ] 和 rightLessMin [ ]。而这两个数组的更新，是需要所有高度的。

解法二中，我们更新一次 heights，就利用之前的算法，求一遍 leftLessMin [ ] 和 rightLessMin [ ]，然后更新面积。而其实，我们求 leftLessMin [ ] 和 rightLessMin [ ] 可以利用之前的 leftLessMin [ ] 和 rightLessMin [ ] 来更新本次的。

我们回想一下 leftLessMin [ ] 和 rightLessMin [ ] 的含义， leftLessMin [ i ] 代表左边第一个比当前柱子矮的下标，如下图橙色柱子时当前遍历的柱子。rightLessMin [ ] 时右边第一个。

left 和 right 是对称关系，下边只考虑 left 的求法。

如下图，如果当前新增的层全部是 1，当然这时最完美的情况，那么 leftLessMin [ ] 根本不需要改变。

然而事实是残酷的，一定会有 0 的出现。

我们考虑最后一个柱子的更新。上一层的 leftLessMin = 1，也就是蓝色 0 的位置是第一个比它低的柱子。但是在当前层，由于中间出现了 0。所以不再是之前的 leftLessMin ，而是和上次出现 0 的位置进行比较（因为 0 一定比当前柱子小），谁的下标大，更接近当前柱子，就选择谁。上图中出现 0 的位置是 2，之前的 leftLessMin 是 1，选一个较大的，那就是 2 了。

###java

public int maximalRectangle4(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    int maxArea = 0;
    int cols = matrix[0].length;
    int[] leftLessMin = new int[cols];
    int[] rightLessMin = new int[cols];
    Arrays.fill(leftLessMin, -1); //初始化为 -1，也就是最左边
    Arrays.fill(rightLessMin, cols); //初始化为 cols，也就是最右边
    int[] heights = new int[cols];
    for (int row = 0; row < matrix.length; row++) {
        //更新所有高度
        for (int col = 0; col < cols; col++) {
            if (matrix[row][col] == '1') {
                heights[col] += 1;
            } else {
                heights[col] = 0;
            }
        }
//更新所有leftLessMin
        int boundary = -1; //记录上次出现 0 的位置
        for (int col = 0; col < cols; col++) {
            if (matrix[row][col] == '1') {
                //和上次出现 0 的位置比较
                leftLessMin[col] = Math.max(leftLessMin[col], boundary);
            } else {
                //当前是 0 代表当前高度是 0，所以初始化为 -1，防止对下次循环的影响
                leftLessMin[col] = -1; 
                //更新 0 的位置
                boundary = col;
            }
        }
        //右边同理
        boundary = cols;
        for (int col = cols - 1; col >= 0; col--) {
            if (matrix[row][col] == '1') {
                rightLessMin[col] = Math.min(rightLessMin[col], boundary);
            } else {
                rightLessMin[col] = cols;
                boundary = col;
            }
        }

        //更新所有面积
        for (int col = cols - 1; col >= 0; col--) {
            int area = (rightLessMin[col] - leftLessMin[col] - 1) * heights[col];
            maxArea = Math.max(area, maxArea);
        }

    }
    return maxArea;

}

时间复杂度：O（mn）。

空间复杂度：O（n）。

总

有时候，如果可以把题抽象到已解决的问题当中去，可以大大的简化问题，很酷！

方法一：动态规划

假设字符串 $s_1$ 和 $s_2$ 的长度分别为 $m$ 和 $n$，创建 $m+1$ 行 $n+1$ 列的二维数组 $\textit{dp}$，其中 $\textit{dp}[i][j]$ 表示使 $s_1[0:i]$ 和 $s_2[0:j]$ 相同的最小 $\text{ASCII}$ 删除和。

上述表示中，$s_1[0:i]$ 表示 $s_1$ 的长度为 $i$ 的前缀，$s_2[0:j]$ 表示 $s_2$ 的长度为 $j$ 的前缀。

动态规划的边界情况如下：

• 当 $i=j=0$ 时，$s_1[0:i]$ 和 $s_2[0:j]$ 都为空，两个空字符串相同，不需要删除任何字符，因此有 $\textit{dp}[0][0]=0$；

• 当 $i=0$ 且 $j>0$ 时，$s_1[0:i]$ 为空且 $s_2[0:j]$ 不为空，空字符串和任何字符串要变成相同，只有将另一个字符串的字符全部删除，因此对任意 $1 \le j \le n$，有 $\textit{dp}[0][j]=\textit{dp}[0][j-1]+s_2[j-1]$；

• 当 $j=0$ 且 $i>0$ 时，$s_2[0:j]$ 为空且 $s_1[0:i]$ 不为空，同理可得，对任意 $1 \le i \le m$，有 $\textit{dp}[i][0]=\textit{dp}[i-1][0]+s_1[i-1]$。

当 $i>0$ 且 $j>0$ 时，考虑 $\textit{dp}[i][j]$ 的计算：

• 当 $s_1[i-1]=s_2[j-1]$ 时，将这两个相同的字符称为公共字符，考虑使 $s_1[0:i-1]$ 和 $s_2[0:j-1]$ 相同的最小 $\text{ASCII}$ 删除和，增加一个公共字符之后，最小 $\text{ASCII}$ 删除和不变，因此 $\textit{dp}[i][j]=\textit{dp}[i-1][j-1]$。

• 当 $s_1[i-1] \ne s_2[j-1]$ 时，考虑以下两项：

  • 使 $s_1[0:i-1]$ 和 $s_2[0:j]$ 相同的最小 $\text{ASCII}$ 删除和，加上删除 $s_1[i-1]$ 的 $\text{ASCII}$ 值；

  • 使 $s_1[0:i]$ 和 $s_2[0:j-1]$ 相同的最小 $\text{ASCII}$ 删除和，加上删除 $s_2[j-1]$ 的 $\text{ASCII}$ 值。

  要得到使 $s_1[0:i]$ 和 $s_2[0:j]$ 相同的最小 $\text{ASCII}$ 删除和，应取两项中较小的一项，因此 $\textit{dp}[i][j]=\min(\textit{dp}[i-1][j]+s_1[i-1],\textit{dp}[i][j-1]+s_2[j-1])$。

由此可以得到如下状态转移方程：

$$
\textit{dp}[i][j] = \begin{cases}
\textit{dp}[i-1][j-1], & s_1[i-1]=s_2[j-1] \
\min(\textit{dp}[i-1][j]+s_1[i-1],\textit{dp}[i][j-1]+s_2[j-1]), & s_1[i-1] \ne s_2[j-1]
\end{cases}
$$

最终计算得到 $\textit{dp}[m][n]$ 即为使 $s_1$ 和 $s_2$ 相同的最小 $\text{ASCII}$ 删除和。

实现方面，需要将 $s_1[i-1]$ 和 $s_2[j-1]$ 转换成相应的 $\text{ASCII}$ 值。

###Java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.codePointAt(i - 1);
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + s2.codePointAt(j - 1);
        }
        for (int i = 1; i <= m; i++) {
            int code1 = s1.codePointAt(i - 1);
            for (int j = 1; j <= n; j++) {
                int code2 = s2.codePointAt(j - 1);
                if (code1 == code2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + code1, dp[i][j - 1] + code2);
                }
            }
        }
        return dp[m][n];
    }
}

###C#

public class Solution {
    public int MinimumDeleteSum(string s1, string s2) {
        int m = s1.Length, n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i, 0] = dp[i - 1, 0] + s1[i - 1];
        }
        for (int j = 1; j <= n; j++) {
            dp[0, j] = dp[0, j - 1] + s2[j - 1];
        }
        for (int i = 1; i <= m; i++) {
            int code1 = s1[i - 1];
            for (int j = 1; j <= n; j++) {
                int code2 = s2[j - 1];
                if (code1 == code2) {
                    dp[i, j] = dp[i - 1, j - 1];
                } else {
                    dp[i, j] = Math.Min(dp[i - 1, j] + code1, dp[i, j - 1] + code2);
                }
            }
        }
        return dp[m, n];
    }
}

###JavaScript

var minimumDeleteSum = function(s1, s2) {
    const m = s1.length, n = s2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] + s1[i - 1].charCodeAt();
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] + s2[j - 1].charCodeAt();
    }
    for (let i = 1; i <= m; i++) {
        const code1 = s1[i - 1].charCodeAt();
        for (let j = 1; j <= n; j++) {
            const code2 = s2[j - 1].charCodeAt();
            if (code1 === code2) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j] + code1, dp[i][j - 1] + code2);
            }
        }
    }
    return dp[m][n];
};

###Python

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + ord(s1[i - 1]), dp[i][j - 1] + ord(s2[j - 1]))
        
        return dp[m][n]

###C++

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i <= m; ++i) {
            dp[i][0] = dp[i - 1][0] + s1[i - 1];
        }
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = dp[0][j - 1] + s2[j - 1];
        }
        for (int i = 1; i <= m; i++) {
            char c1 = s1[i - 1];
            for (int j = 1; j <= n; j++) {
                char c2 = s2[j - 1];
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
                }
            }
        }

        return dp[m][n];
    }
};

###Go

func minimumDeleteSum(s1 string, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        if i > 0 {
            dp[i][0] = dp[i-1][0] + int(s1[i-1])
        }
    }
    for j := range dp[0] {
        if j > 0 {
            dp[0][j] = dp[0][j-1] + int(s2[j-1])
        }
    }
    for i, c1 := range s1 {
        for j, c2 := range s2 {
            if c1 == c2 {
                dp[i+1][j+1] = dp[i][j]
            } else {
                dp[i+1][j+1] = min(dp[i][j+1] + int(c1), dp[i+1][j] + int(c2))
            }
        }
    }
    return dp[m][n]
}

###C

int minimumDeleteSum(char* s1, char* s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)malloc((n + 1) * sizeof(int));
    }
    
    dp[0][0] = 0;
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] + s1[i - 1];
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] + s2[j - 1];
    }
    for (int i = 1; i <= m; i++) {
        char c1 = s1[i - 1];
        for (int j = 1; j <= n; j++) {
            char c2 = s2[j - 1];
            if (c1 == c2) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = fmin(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
            }
        }
    }
    
    int result = dp[m][n];    
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

###TypeScript

function minimumDeleteSum(s1: string, s2: string): number {
    const m = s1.length;
    const n = s2.length;
    
    const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] + s1.charCodeAt(i - 1);
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] + s2.charCodeAt(j - 1);
    }
    for (let i = 1; i <= m; i++) {
        const c1 = s1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = s2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + s1.charCodeAt(i - 1),
                    dp[i][j - 1] + s2.charCodeAt(j - 1)
                );
            }
        }
    }
    
    return dp[m][n];
}

###Rust

impl Solution {
    pub fn minimum_delete_sum(s1: String, s2: String) -> i32 {
        let m = s1.len();
        let n = s2.len();
        let s1_bytes = s1.as_bytes();
        let s2_bytes = s2.as_bytes();
        
        let mut dp = vec![vec![0; n + 1]; m + 1];
        for i in 1..=m {
            dp[i][0] = dp[i - 1][0] + s1_bytes[i - 1] as i32;
        }
        for j in 1..=n {
            dp[0][j] = dp[0][j - 1] + s2_bytes[j - 1] as i32;
        }
        for i in 1..=m {
            for j in 1..=n {
                if s1_bytes[i - 1] == s2_bytes[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = std::cmp::min(
                        dp[i - 1][j] + s1_bytes[i - 1] as i32,
                        dp[i][j - 1] + s2_bytes[j - 1] as i32
                    );
                }
            }
        }
        
        dp[m][n]
    }
}

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是字符串 $s_1$ 和 $s_2$ 的长度。二维数组 $\textit{dp}$ 有 $m+1$ 行和 $n+1$ 列，需要对 $\textit{dp}$ 中的每个元素进行计算。

• 空间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是字符串 $s_1$ 和 $s_2$ 的长度。创建了 $m+1$ 行 $n+1$ 列的二维数组 $\textit{dp}$。

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

 

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

 

提示:

• 0 <= s1.length, s2.length <= 1000
• s1 和 s2 由小写英文字母组成

用 $s_1$ 和 $s_2$ 的 ASCII 值之和，减去保留的 ASCII 之和的最大值，就是删除字符的 ASCII 值之和的最小值。

计算最多保留的 ASCII 之和，方法和 1143. 最长公共子序列 一样：

• 1143 题，$s_1[i] = s_2[j]$ 时，都保留，最长公共子序列长度增加 $1$。
• 本题，$s_1[i] = s_2[j]$ 时，都保留，保留的 ASCII 之和增加 $\text{ASCII}(s_1[i])\cdot 2$。

所以只需把 1143 题的 $+1$ 改成 $+\text{ASCII}(s_1[i])\cdot 2$。

也可以改成 $+\text{ASCII}(s_1[i])$，最后返回时再乘以 $2$。

###py

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n, m = len(s1), len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(s1):
            for j, y in enumerate(s2):
                if x == y:
                    f[i + 1][j + 1] = f[i][j] + ord(x)
                else:
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j])
        return total - f[n][m] * 2

###java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int total = s1.chars().sum() + s2.chars().sum();

        char[] s = s1.toCharArray();
        char[] t = s2.toCharArray();
        int n = s.length;
        int m = t.length;

        int[][] f = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i] == t[j]) {
                    f[i + 1][j + 1] = f[i][j] + s[i];
                } else {
                    f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        return total - f[n][m] * 2;
    }
}

###cpp

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        int total = reduce(s1.begin(), s1.end(), 0) + reduce(s2.begin(), s2.end(), 0);

        vector f(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s1[i] == s2[j]) {
                    f[i + 1][j + 1] = f[i][j] + s1[i];
                } else {
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]);
                }
            }
        }
        return total - f[n][m] * 2;
    }
};

###go

func minimumDeleteSum(s1, s2 string) int {
n, m := len(s1), len(s2)
total := 0
for _, c := range s1 {
total += int(c)
}
for _, c := range s2 {
total += int(c)
}

f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for i, x := range s1 {
for j, y := range s2 {
if x == y {
f[i+1][j+1] = f[i][j] + int(x)
} else {
f[i+1][j+1] = max(f[i][j+1], f[i+1][j])
}
}
}
return total - f[n][m]*2
}

空间优化：

###py

# 更快的写法见【Python3 手写 max】
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [0] * (m + 1)
        for x in s1:
            ord_x = ord(x)
            pre = 0  # f[0]
            for j, y in enumerate(s2):
                tmp = f[j + 1]
                if x == y:
                    f[j + 1] = pre + ord_x
                else:
                    f[j + 1] = max(f[j + 1], f[j])
                pre = tmp
        return total - f[m] * 2

###py

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s2)
        total = sum(map(ord, s1)) + sum(map(ord, s2))

        f = [0] * (m + 1)
        for x in s1:
            ord_x = ord(x)
            pre = 0  # f[0]
            for j, y in enumerate(s2):
                tmp = f[j + 1]
                if x == y:
                    f[j + 1] = pre + ord_x
                elif f[j] > f[j + 1]:
                    f[j + 1] = f[j]
                pre = tmp
        return total - f[m] * 2

###java

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int total = s1.chars().sum() + s2.chars().sum();

        char[] s = s1.toCharArray();
        char[] t = s2.toCharArray();
        int m = t.length;

        int[] f = new int[m + 1];
        for (char x : s) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                if (x == t[j]) {
                    f[j + 1] = pre + x;
                } else {
                    f[j + 1] = Math.max(f[j + 1], f[j]);
                }
                pre = tmp;
            }
        }
        return total - f[m] * 2;
    }
}

###cpp

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s2.size();
        int total = reduce(s1.begin(), s1.end(), 0) + reduce(s2.begin(), s2.end(), 0);

        vector<int> f(m + 1);
        for (char x : s1) {
            int pre = 0; // f[0]
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                if (x == s2[j]) {
                    f[j + 1] = pre + x;
                } else {
                    f[j + 1] = max(f[j + 1], f[j]);
                }
                pre = tmp;
            }
        }
        return total - f[m] * 2;
    }
};

###go

func minimumDeleteSum(s1, s2 string) int {
m := len(s2)
total := 0
for _, c := range s1 {
total += int(c)
}
for _, c := range s2 {
total += int(c)
}

f := make([]int, m+1)
for _, x := range s1 {
pre := 0 // f[0]
for j, y := range s2 {
tmp := f[j+1]
if x == y {
f[j+1] = pre + int(x)
} else {
f[j+1] = max(f[j+1], f[j])
}
pre = tmp
}
}
return total - f[m]*2
}

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $s_1$ 的长度，$m$ 是 $s_2$ 的长度。
• 空间复杂度：$\mathcal{O}(m)$。

专题训练

见下面动态规划题单的「§4.1 最长公共子序列（LCS）」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果想要查看作者更多文章，可以点击此处！！！🔥🔥🔥

为了本篇文章更好的观感，可以点击此处！！！

1143. 最长公共子序列

583. 两个字符串的删除操作

712. 两个字符串的最小ASCII删除和

---

「最长递增子序列」针对一个字符串，求出其最长递增子序列 (废话文学！！) 详细介绍可见 动态规划设计：最长递增子序列

「最长重复子数组」针对两个数组，求出其最长重复子数组 (子数组必须要连着) 详细介绍可见 最长重复子数组

而我们今天要介绍的是「最长公共子序列」，它是针对两个字符串，求出其最长公共子序列 (子序列可以不用连着)

模版归纳

首先结合题目 最长公共子序列，归纳总结出「最长公共子序列」问题的模版

毫无疑问这种类型的题目需要使用「DP」去解决！！这里给出一个例子 s1 = "abcde", s2 = "ace" ，下面所有分析都围绕该样例展开

先给出 dp[][] 数组的定义：dp[i][j] 表示子串 s1[0..i] 和 s2[0..j] 最长公共子序列的长度

那么「状态转移方程」是什么呢？

• 如果 s1[i] = s2[j]，dp[i][j] = dp[i - 1][j - 1] + 1
• 如果 s1[i] != s2[j]，dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])

为什么就是这样转移的呢？直接看下图：

那么「base case」是什么呢？

如上图粉色标记出来的就是 base case。橙色标记出来的是相等的情况，其余是不等的情况

完整模版

###java

public int longestCommonSubsequence(String text1, String text2) {
    int n1 = text1.length(), n2 = text2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            char c1 = text1.charAt(i - 1);
            char c2 = text2.charAt(j - 1);
            // 相等情况
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1;
            // 不等情况
            else dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return dp[n1][n2];
}

✨ 如何输出最长公共子序列

「最长公共子序列」问题基本都是要求返回一个最值即可，但是有时候面试官喜欢不按常理出牌，让你输出最长公共子序列

我们可以通过构造出来的二维 dp 数组来得到最长公共子序列。如下图所示，从最后一个点开始往左上角的方向遍历

如果 s1[i] = s2[j]，那么当前字符肯定在最长公共子序列中；否在我们就向左或者向上遍历

至于选择「向左」还是「向上」的方向，这就要和构造 dp 的时候联系起来。我们是挑了一个最大值，所以遍历的方向也是谁大就往谁的方向遍历

###java

public int longestCommonSubsequence(String text1, String text2) {
    
    // 同上面的模版
    
    /* ------- print ------- */
    int i = n1, j = n2;
    StringBuffer sb = new StringBuffer();
    while (i > 0 && j > 0) {
        char c1 = text1.charAt(i - 1);
        char c2 = text2.charAt(j - 1);
        if (c1 == c2) {
            sb.append(c1);
            // 向左上角遍历
            i--; j--;
        } else {
            // 向上
            if (dp[i - 1][j] > dp[i][j - 1]) i--;
            // 向左
            else j--;
        }
    }
    System.out.println(sb.reverse());
    /* ------- end ------- */
    return dp[n1][n2];
}

两个字符串的最小ASCII删除和

题目详情可见 两个字符串的最小ASCII删除和

其实这个题目的底层也是「最长公共子序列」，只是问法稍微变化了一点

「需要被删除的字符 = 原字符串 - 最长公共子序列」

结合这个题目我们把 dp[][] 数组的定义稍微改改：dp[i][j] 表示子串 s1[0..i] 和 s2[0..j] 最小 ASCII 删除和

那么「状态转移方程」是什么呢？(有点逆过程的意思！！！)

• 如果 s1[i] = s2[j]，dp[i][j] = dp[i - 1][j - 1] (不需要被删除)
• 如果 s1[i] != s2[j]，dp[i][j] = Math.min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j])

那么「base case」是什么呢？

如上图粉色标记出来的就是 base case，e 表示 e 的 ASCII 值

###java

public int minimumDeleteSum(String s1, String s2) {
    int n1 = s1.length(), n2 = s2.length();
    int[][] dp = new int[n1 + 1][n2 + 1];
    // base case
    for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
    for (int i = 1; i <= n2; i++) dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            int c1 = s1.charAt(i - 1);
            int c2 = s2.charAt(j - 1);
            // 相等情况
            if (c1 == c2) dp[i][j] = dp[i - 1][j - 1];
            // 不等情况
            else dp[i][j] = Math.min(dp[i][j - 1] + c2, dp[i - 1][j] + c1);
        }
    }
    return dp[n1][n2];
}

首先给出LCS的模板解法：

int longestCommonSubsequence(string text1, string text2)
{
    int LCS[text1.size() + 1][text2.size() + 1];
    memset(LCS,0, sizeof(LCS));

    for (int i = 1; i <= text1.size(); ++i)
        for (int j = 1; j <= text2.size(); ++j)
        {
            if(text1[i - 1] == text2[j - 1])
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
            else
                LCS[i][j] = max(LCS[i - 1][j],LCS[i][j - 1]);
        }
    return LCS[text1.size()][text2.size()];
}

那么如何改造这个模板来让他适应我们的问题呢？
因为在求LCS的时候我们是按照构造一个dp[i][j]表示以str1的第i项为结尾，str2的第j项为结尾，那么就会有：（LCS(i,j) <=> dp[i][j]）

--------------------------------------
 * if(str1.n == str2.m):
 *      LCS(n,m) = LCS(n - 1,m - 1) + 1
 * else
 *      LCS(n,m) = max{LCS(n - 1,m),LCS(n,m - 1)}
--------------------------------------

所以我们就会有一种想法，对这个LCS求解的dp过程在进行一次约数，肯定可以得到我们的目标LCS

int minimumDeleteSum(string s1, string s2)
{
    int len1 = s1.length();
    int len2 = s2.length();

    int dp[len1 + 1][len2 + 1];
    memset(dp,0, sizeof(dp));

    for (int i = 1; i <= len1; ++i)
        for (int j = 1; j <= len2; ++j)
        {
            if(s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + s1[i - 1];
            else
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
        }

    int sum = 0;
    for (int i = 0; i < len1; ++i)
        sum += s1[i];
    for (int i = 0; i < len2; ++i)
        sum += s2[i];
    return sum - 2 * dp[len1][len2];
}

别忘了最后返回的值是两个string的ASCII和减去两个LCS的ASCII的sum哦

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。

返回包含原始树中所有 最深节点 的 最小子树 。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。

一个节点的 子树 是该节点加上它的所有后代的集合。

 

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

 

提示：

• 树中节点的数量在 [1, 500] 范围内。
• 0 <= Node.val <= 500
• 每个节点的值都是 独一无二 的。

 

注意：本题与力扣 1123 重复：https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves

前置题目：236. 二叉树的最近公共祖先。

视频讲解：二叉树的最近公共祖先【基础算法精讲 12】。

方法一：递归递归，有递有归

{:width=360px}

看上图（示例 1），这棵树的节点 $3,5,2$ 都是最深叶节点 $7,4$ 的公共祖先，但只有节点 $2$ 是最近的公共祖先。

上面视频中提到，如果我们要找的节点只在左子树中，那么最近公共祖先也必然只在左子树中。对于本题，如果左子树的最大深度比右子树的大，那么最深叶结点就只在左子树中，所以最近公共祖先也只在左子树中。

如果左右子树的最大深度一样呢？当前节点一定是最近公共祖先吗？

不一定。比如节点 $1$ 的左右子树最深叶节点 $0,8$ 的深度都是 $2$，但该深度并不是全局最大深度，所以节点 $1$ 并不能是答案。

根据以上讨论，正确做法如下：

1. 递归这棵二叉树，同时维护全局最大深度 $\textit{maxDepth}$。
2. 在「递」的时候往下传 $\textit{depth}$，用来表示当前节点的深度。
3. 在「归」的时候往上传当前子树最深叶节点的深度。
4. 设左子树最深叶节点的深度为 $\textit{leftMaxDepth}$，右子树最深叶节点的深度为 $\textit{rightMaxDepth}$。如果 $\textit{leftMaxDepth}=\textit{rightMaxDepth}=\textit{maxDepth}$，那么更新答案为当前节点。⚠注意：这并不代表我们立刻找到了答案，如果后面发现了更深的叶节点，答案还会更新。

class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        max_depth = -1  # 全局最大深度
        ans = None

        def dfs(node: Optional[TreeNode], depth: int) -> int:
            nonlocal ans, max_depth
            if node is None:
                max_depth = max(max_depth, depth)  # 维护全局最大深度
                return depth

            left_max_depth = dfs(node.left, depth + 1)  # 获取左子树最深叶节点的深度
            right_max_depth = dfs(node.right, depth + 1)  # 获取右子树最深叶节点的深度

            if left_max_depth == right_max_depth == max_depth:
                ans = node  # node 可能是答案

            return max(left_max_depth, right_max_depth)  # 当前子树最深叶节点的深度

        dfs(root, 0)
        return ans

class Solution {
    private int maxDepth = -1; // 全局最大深度
    private TreeNode ans;

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private int dfs(TreeNode node, int depth) {
        if (node == null) {
            maxDepth = Math.max(maxDepth, depth); // 维护全局最大深度
            return depth;
        }

        int leftMaxDepth = dfs(node.left, depth + 1); // 获取左子树最深叶节点的深度
        int rightMaxDepth = dfs(node.right, depth + 1); // 获取右子树最深叶节点的深度

        if (leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth) {
            ans = node; // node 可能是答案
        }

        return Math.max(leftMaxDepth, rightMaxDepth); // 当前子树最深叶节点的深度
    }
}

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        int max_depth = -1; // 全局最大深度
        TreeNode* ans;

        auto dfs = [&](this auto&& dfs, TreeNode* node, int depth) {
            if (node == nullptr) {
                max_depth = max(max_depth, depth); // 维护全局最大深度
                return depth;
            }

            int left_max_depth = dfs(node->left, depth + 1); // 获取左子树最深叶节点的深度
            int right_max_depth = dfs(node->right, depth + 1); // 获取右子树最深叶节点的深度

            if (left_max_depth == right_max_depth && left_max_depth == max_depth) {
                ans = node; // node 可能是答案
            }

            return max(left_max_depth, right_max_depth); // 当前子树最深叶节点的深度
        };

        dfs(root, 0);
        return ans;
    }
};

func subtreeWithAllDeepest(root *TreeNode) (ans *TreeNode) {
    maxDepth := -1 // 全局最大深度

    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, depth int) int {
        if node == nil {
            maxDepth = max(maxDepth, depth) // 维护全局最大深度
            return depth
        }

        leftMaxDepth := dfs(node.Left, depth+1) // 获取左子树最深叶节点的深度
        rightMaxDepth := dfs(node.Right, depth+1) // 获取右子树最深叶节点的深度

        if leftMaxDepth == rightMaxDepth && leftMaxDepth == maxDepth {
            ans = node // node 可能是答案
        }

        return max(leftMaxDepth, rightMaxDepth) // 当前子树最深叶节点的深度
    }

    dfs(root, 0)
    return
}

var subtreeWithAllDeepest = function(root) {
    let maxDepth = -1; // 全局最大深度
    let ans = null;

    function dfs(node, depth) {
        if (node === null) {
            maxDepth = Math.max(maxDepth, depth); // 维护全局最大深度
            return depth;
        }

        const leftMaxDepth = dfs(node.left, depth + 1); // 获取左子树最深叶节点的深度
        const rightMaxDepth = dfs(node.right, depth + 1); // 获取右子树最深叶节点的深度

        if (leftMaxDepth === rightMaxDepth && leftMaxDepth === maxDepth) {
            ans = node; // node 可能是答案
        }

        return Math.max(leftMaxDepth, rightMaxDepth); // 当前子树最深叶节点的深度
    }

    dfs(root, 0);
    return ans;
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。每个节点都会恰好访问一次。
• 空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树是一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

方法二：自底向上

也可以不用全局变量，而是把每棵子树都看成是一个「子问题」，即对于每棵子树，我们需要知道：

• 这棵子树最深叶结点的深度。这里是指叶子在这棵子树内的深度，而不是在整棵二叉树的视角下的深度。相当于这棵子树的高度。
• 这棵子树的最深叶结点的最近公共祖先 $\textit{lca}$。

分类讨论：

• 设子树的根节点为 $\textit{node}$，$\textit{node}$ 的左子树的高度为 $\textit{leftHeight}$，$\textit{node}$ 的右子树的高度为 $\textit{rightHeight}$。
• 如果 $\textit{leftHeight} > \textit{rightHeight}$，那么子树的高度为 $\textit{leftHeight} + 1$，$\textit{lca}$ 是左子树的 $\textit{lca}$。
• 如果 $\textit{leftHeight} < \textit{rightHeight}$，那么子树的高度为 $\textit{rightHeight} + 1$，$\textit{lca}$ 是右子树的 $\textit{lca}$。
• 如果 $\textit{leftHeight} = \textit{rightHeight}$，那么子树的高度为 $\textit{leftHeight} + 1$，$\textit{lca}$ 就是 $\textit{node}$。反证法：如果 $\textit{lca}$ 在左子树中，那么 $\textit{lca}$ 不是右子树的最深叶结点的祖先，这不对；如果 $\textit{lca}$ 在右子树中，那么 $\textit{lca}$ 不是左子树的最深叶结点的祖先，这也不对；如果 $\textit{lca}$ 在 $\textit{node}$ 的上面，那就不符合「最近」的要求。所以 $\textit{lca}$ 只能是 $\textit{node}$。

class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node: Optional[TreeNode]) -> Tuple[int, Optional[TreeNode]]:
            if node is None:
                return 0, None

            left_height, left_lca = dfs(node.left)
            right_height, right_lca = dfs(node.right)

            if left_height > right_height:  # 左子树更高
                return left_height + 1, left_lca
            if left_height < right_height:  # 右子树更高
                return right_height + 1, right_lca
            return left_height + 1, node  # 一样高

        return dfs(root)[1]

class Solution {
    private record Pair(int height, TreeNode lca) {}

    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).lca;
    }

    private Pair dfs(TreeNode node) {
        if (node == null) {
            return new Pair(0, null);
        }

        Pair left = dfs(node.left);
        Pair right = dfs(node.right);

        if (left.height > right.height) { // 左子树更高
            return new Pair(left.height + 1, left.lca);
        }
        if (left.height < right.height) { // 右子树更高
            return new Pair(right.height + 1, right.lca);
        }
        return new Pair(left.height + 1, node); // 一样高
    }
}

class Solution {
    pair<int, TreeNode*> dfs(TreeNode* node) {
        if (node == nullptr) {
            return {0, nullptr};
        }

        auto [left_height, left_lca] = dfs(node->left);
        auto [right_height, right_lca] = dfs(node->right);

        if (left_height > right_height) { // 左子树更高
            return {left_height + 1, left_lca};
        }
        if (left_height < right_height) { // 右子树更高
            return {right_height + 1, right_lca};
        }
        return {left_height + 1, node}; // 一样高
    }

public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
};

func dfs(node *TreeNode) (int, *TreeNode) {
    if node == nil {
        return 0, nil
    }

    leftHeight, leftLCA := dfs(node.Left)
    rightHeight, rightLCA := dfs(node.Right)

    if leftHeight > rightHeight { // 左子树更高
        return leftHeight + 1, leftLCA
    }
    if leftHeight < rightHeight { // 右子树更高
        return rightHeight + 1, rightLCA
    }
    return leftHeight + 1, node // 一样高
}

func subtreeWithAllDeepest(root *TreeNode) *TreeNode {
    _, lca := dfs(root)
    return lca
}

function dfs(node) {
    if (node === null) {
        return [0, null];
    }

    const [leftHeight, leftLca] = dfs(node.left);
    const [rightHeight, rightLca] = dfs(node.right);

    if (leftHeight > rightHeight) { // 左子树更高
        return [leftHeight + 1, leftLca];
    }
    if (leftHeight < rightHeight) { // 右子树更高
        return [rightHeight + 1, rightLca];
    }
    return [leftHeight + 1, node]; // 一样高
}

var subtreeWithAllDeepest = function(root) {
    return dfs(root)[1];
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$。每个节点都会恰好访问一次。
• 空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树是一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

看了下下面的题解，除了官方题解用多个返回值只遍历了一次，其他题解大都反复计算深度，其实复杂度是O(nlogn)
本题解进行一次遍历得到结果

主要思想：

在一次遍历深度的过程中，找到左右子树深度都为最大值的节点记录下来

class Solution {
  private int maxDeep = Integer.MIN_VALUE;
  private TreeNode result;
  public TreeNode subtreeWithAllDeepest(TreeNode root) {
    maxDeep(root, 0);
    return result;
  }
  private int maxDeep(TreeNode node, int deep) {
    if (node == null) {
      return deep;
    }
    int left = maxDeep(node.left, deep+1);
    int right = maxDeep(node.right, deep+1);
    int currentMax = Math.max(left, right);
    maxDeep = Math.max(maxDeep, currentMax);
    if (left == maxDeep && right == maxDeep) {
      result = node;
    }
    return currentMax;
  }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    // 思路：从每个树开始，获得当前节点的左右子树的最大深度
    // 深度相同，说明最深的节点在这个节点两边，那这个节点就是结果
    // 如果深度不相同，则去深度大的子树继续判断，最终就能得到结果
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        if (root == null) return root;

        // 获取当前节点的左右子树的最大深度
        int leftMaxDepth = getMaxDepth(root.left);
        int rightMaxDepth = getMaxDepth(root.right);

        // 如果两边最大深度相同，则这个节点就是结果
        if (leftMaxDepth == rightMaxDepth) return root;

        // 不相等，那就去深度大的子树那边继续找
        if (leftMaxDepth > rightMaxDepth){
            return subtreeWithAllDeepest(root.left);
        }

        return subtreeWithAllDeepest(root.right);
    }

    public int getMaxDepth(TreeNode root){
        if (root == null) return 0;

        return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
    }
}

• 知识点：动态规划
• 时间复杂度：O(n*m)；n，m 分别为两个序列的长度。

动态规划题目一般要先想好两个问题：

• 状态如何定义。
• 状态之间如何转移。

对于该题，最终目标是在分别两个序列中选取等长且非空的子序列，使得两个子序列的点积最大。
即，在 nums1 的前 n 个数中，在 nums2 的前 m 个数字中分别选取等长且非空的子序列， 使其点积最大。
推而广之，我们可以将问题表示为，在nums1的前 x (x <= n)个数字中，在nums2的前y(y <= m)个数字中，分别选取等长且非空的子序列， 使其点积最大。
为了方便，我们用 f(x, y) 表示子问题的最优方案的点积。
当(x, y) = (n,m) 时，f(x,y) 就是最终答案。

状态转移主要是分析状态之间的关联或差异，利用小问题的解高效的构造大问题的解。
来思考下该题状态如何转移，该题的特点是小问题总是为大问题的前缀，总是可以向小问题中追加数字得到一个大问题。
设 nx = nums1[x]，ny = nums2[y]。
f(x,y) 可能由以下几个状态转移得到：

• 向 f(x-1, y-1) 追加 nx,ny 获得 f(x, y)。
• 向 f(x, y-1) 追加 ny 获得 f(x, y)。
• 向 f(x-1, y) 追加 nx 获得 f(x,y)。

当然，也可以同时追加多个数字，由更小的问题获得 f(x, y)，但这本质上还是通过上述三种子问题间接转移过来的。
那么，为何f(x-1，y-1) 不能用 f(x-1, y) 或者 f(x, y-1) 间接转移过来呢？因为在求解过程中要考虑nx 和 ny 在对应位置的情况。
总结一下，该题的状态方程如下：
$$
f(x,y) = max \left{ \begin{array}{c}
nxny&, 有且只有 nx，ny\
nxny + f(x-1, y-1)&, 包含 nx，ny \
f(x, y-1)&, 不包含 nx \
f(x-1, y)&, 不包含 ny \
f(x-1, y-1)&, 不包含 nx，ny\
\end{array}\right.
$$

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int dp[501][501];
        for(int i = 0; i <= nums1.size(); i++) {
            for(int j = 0; j <= nums2.size(); j++) {
                dp[i][j] = -1000*1000*500;
            }
        }
        for(int i = 1; i <= nums1.size(); i++) {
            for(int j = 1; j <= nums2.size(); j++) {
                int a = nums1[i-1];
                int b = nums2[j-1];
                dp[i][j] = max(dp[i][j], a*b);
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + a*b);
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
                dp[i][j] = max(dp[i][j], dp[i-1][j]);
                dp[i][j] = max(dp[i][j], dp[i][j-1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

如果感觉有点意思，可以关注👏HelloNebula👏

• 分享周赛题解
• 分享计算机专业课知识
• 分享C++相关岗位面试题
• 分享专业书籍PDF

给你两个数组 nums1 和 nums2 。

请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

 

示例 1：

输入：nums1 = [2,1,-2,5], nums2 = [3,0,-6]
输出：18
解释：从 nums1 中得到子序列 [2,-2] ，从 nums2 中得到子序列 [3,-6] 。
它们的点积为 (2*3 + (-2)*(-6)) = 18 。

示例 2：

输入：nums1 = [3,-2], nums2 = [2,-6,7]
输出：21
解释：从 nums1 中得到子序列 [3] ，从 nums2 中得到子序列 [7] 。
它们的点积为 (3*7) = 21 。

示例 3：

输入：nums1 = [-1,-1], nums2 = [1,1]
输出：-1
解释：从 nums1 中得到子序列 [-1] ，从 nums2 中得到子序列 [1] 。
它们的点积为 -1 。

 

提示：

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 1000

 

点积：

定义 a = [a1, a2,…, an] 和 b = [b1, b2,…, bn] 的点积为：



这里的 Σ 指示总和符号。

一、寻找子问题

为方便描述，下文把 $\textit{nums}_1$ 和 $\textit{nums}_2$ 简称为 $a$ 和 $b$。

在示例 1 中，我们要解决的问题（原问题）是：

• 从 $a=[2,1,-2,5]$ 和 $b=[3,0,-6]$ 中选两个长度相等的非空子序列 $c$ 和 $d$，计算 $c$ 和 $d$ 的点积的最大值。

⚠注意：选出的子序列必须是非空的。

考虑从右往左选数字，用「选或不选」分类讨论：

• 选 $a[3]$ 和 $b[2]$，需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0]$ 中选两个长度相等的子序列，计算两个子序列点积的最大值。由于我们选了元素，所以子序列可以为空。但这样思考的话，子问题就和原问题不相似了。为了保证子问题和原问题相似，我们可以再细分为两种情况：
  • 选 $a[3]$ 和 $b[2]$，且前面不再选数字。这意味着点积就是 $a[3]\cdot b[2]$。
  • 选 $a[3]$ 和 $b[2]$，且前面还要选数字。需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
• 不选 $a[3]$，需要解决的子问题为：从 $a=[2,1,-2]$ 和 $b=[3,0,-6]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。
• 不选 $b[2]$，需要解决的子问题为：从 $a=[2,1,-2,5]$ 和 $b=[3,0]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。

由于选或不选都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。

注 1：从右往左思考，主要是为了方便把递归翻译成递推。从左往右思考也是可以的。

注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。子序列相邻无关一般是「选或不选」，子序列相邻相关（例如 LIS 问题）一般是「枚举选哪个」。本题用到的是「选或不选」。

二、状态定义与状态转移方程

根据上面的讨论，定义状态为 $\textit{dfs}(i,j)$，表示从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。

接下来，思考如何从一个状态转移到另一个状态。

用「选或不选」分类讨论：

• 选 $a[i]$ 和 $b[j]$，且前面不再选数字。这意味着点积就是 $a[i]\cdot b[j]$。
• 选 $a[i]$ 和 $b[j]$，且前面还要选数字。需要解决的子问题为：从 $a$ 的前缀 $[0,i-1]$ 和 $b$ 的前缀 $[0,j-1]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i-1,j-1)$。再加上 $a[i]\cdot b[j]$，就得到了 $\textit{dfs}(i,j)$。
• 前两种情况可以合并为：$\max(\textit{dfs}(i-1,j-1), 0) + a[i]\cdot b[j]$。
• 不选 $a[i]$，需要解决的子问题为：从 $a$ 的前缀 $[0,i-1]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i-1,j)$。
• 不选 $b[j]$，需要解决的子问题为：从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j-1]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值，即 $\textit{dfs}(i,j-1)$。

这四种情况取最大值，就得到了 $\textit{dfs}(i,j)$，即

$$
\textit{dfs}(i,j) = \max{\max(\textit{dfs}(i-1,j-1), 0) + a[i]\cdot b[j], \textit{dfs}(i-1,j),\textit{dfs}(i,j-1)}
$$

递归边界：$\textit{dfs}(-1,j)=\textit{dfs}(i,-1)=-\infty$。此时其中一个数组没有元素，无法选出非空子序列，不合法。用 $-\infty$ 表示不合法的状态，从而保证 $\max$ 不会取到不合法的状态。

递归入口：$\textit{dfs}(n-1,m-1)$，这是原问题，也是答案。其中 $n$ 是 $a$ 的长度，$m$ 是 $b$ 的长度。

三、递归搜索 + 保存递归返回值 = 记忆化搜索

考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

• 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\textit{memo}$ 数组中。
• 如果一个状态不是第一次遇到（$\textit{memo}$ 中保存的结果不等于 $\textit{memo}$ 的初始值），那么可以直接返回 $\textit{memo}$ 中保存的结果。

⚠注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i,j)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$，但本题子序列点积可能是负数，可以初始化为 $\infty$。

Python 用户可以无视上面这段，直接用 @cache 装饰器。

具体请看视频讲解 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。

###py

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        # 返回从 nums1[:i+1] 和 nums2[:j+1] 中选两个长度相同的【非空】子序列的最大点积
        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(i: int, j: int) -> int:
            if i < 0 or j < 0:
                # 其中一个数组没有元素，无法选出非空子序列
                return -inf  # 下面计算 max 不会取到无解情况

            # 选 nums1[i] 和 nums2[j]
            # 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
            res1 = max(dfs(i - 1, j - 1), 0) + nums1[i] * nums2[j]

            # 不选 nums1[i]
            res2 = dfs(i - 1, j)

            # 不选 nums2[j]
            res3 = dfs(i, j - 1)

            return max(res1, res2, res3)

        return dfs(len(nums1) - 1, len(nums2) - 1)

###java

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[][] memo = new int[n][m];
        for (int[] row : memo) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        return dfs(n - 1, m - 1, nums1, nums2, memo);
    }

    // 从 nums1[0,i] 和 nums2[0,j] 中选两个长度相同的【非空】子序列的最大点积
    private int dfs(int i, int j, int[] nums1, int[] nums2, int[][] memo) {
        if (i < 0 || j < 0) {
            // 其中一个数组没有元素，无法选出非空子序列
            return Integer.MIN_VALUE; // 下面计算 max 不会取到无解情况
        }

        if (memo[i][j] != Integer.MAX_VALUE) { // 之前计算过
            return memo[i][j];
        }

        // 选 nums1[i] 和 nums2[j]
        // 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
        int res1 = Math.max(dfs(i - 1, j - 1, nums1, nums2, memo), 0) + nums1[i] * nums2[j];

        // 不选 nums1[i]
        int res2 = dfs(i - 1, j, nums1, nums2, memo);

        // 不选 nums2[j]
        int res3 = dfs(i, j - 1, nums1, nums2, memo);

        memo[i][j] = Math.max(res1, Math.max(res2, res3)); // 记忆化
        return memo[i][j];
    }
}

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector memo(n, vector<int>(m, INT_MAX));

        // 从 nums1[0,i] 和 nums2[0,j] 中选两个长度相同的【非空】子序列的最大点积
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i < 0 || j < 0) {
                // 其中一个数组没有元素，无法选出非空子序列
                return INT_MIN; // 下面计算 max 不会取到无解情况
            }

            int& res = memo[i][j]; // 注意这里是引用
            if (res != INT_MAX) { // 之前计算过
                return res;
            }

            // 选 nums1[i] 和 nums2[j]
            // 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
            res = max(dfs(i - 1, j - 1), 0) + nums1[i] * nums2[j];

            // 不选 nums1[i]
            res = max(res, dfs(i - 1, j));

            // 不选 nums2[j]
            res = max(res, dfs(i, j - 1));

            return res;
        };

        return dfs(n - 1, m - 1);
    }
};

###go

func maxDotProduct(nums1, nums2 []int) int {
n := len(nums1)
m := len(nums2)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, m)
for j := range memo[i] {
memo[i][j] = math.MaxInt
}
}

// 从 nums1[:i+1] 和 nums2[:j+1] 中选两个长度相同的【非空】子序列的最大点积
var dfs func(int, int) int
dfs = func(i, j int) int {
if i < 0 || j < 0 {
// 其中一个数组没有元素，无法选出非空子序列
return math.MinInt // 下面计算 max 不会取到无解情况
}

p := &memo[i][j]
if *p != math.MaxInt { // 之前计算过
return *p
}

// 选 nums1[i] 和 nums2[j]
// 和前面的子序列拼起来，或者不拼（作为子序列的第一个数）
res1 := max(dfs(i-1, j-1), 0) + nums1[i]*nums2[j]

// 不选 nums1[i]
res2 := dfs(i-1, j)

// 不选 nums2[j]
res3 := dfs(i, j-1)

*p = max(res1, res2, res3) // 记忆化
return *p
}

return dfs(n-1, m-1)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(nm)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(nm)$。
• 空间复杂度：$\mathcal{O}(nm)$。保存多少状态，就需要多少空间。

四、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i+1][j+1]$ 的定义和 $\textit{dfs}(i,j)$ 的定义是一样的，都表示从 $a$ 的前缀 $[0,i]$ 和 $b$ 的前缀 $[0,j]$ 中选两个长度相等的非空子序列，计算两个子序列点积的最大值。这里 $+1$ 是为了把 $\textit{dfs}(-1,j)$ 和 $\textit{dfs}(i,-1)$ 也翻译过来，这样我们可以把 $f[0][j]$ 和 $f[i][0]$ 作为初始值。

相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：

$$
f[i+1][j+1] = \max{\max(f[i][j], 0) + a[i]\cdot b[j], f[i][j+1],f[i+1][j]}
$$

初始值：$f$ 第一行和第一列初始化成 $-\infty$，翻译自递归边界 $\textit{dfs}(-1,j)=\textit{dfs}(i,-1)=-\infty$。

答案为 $f[n][m]$，翻译自递归入口 $\textit{dfs}(n-1,m-1)$。

###py

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)
        f = [[-inf] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(nums1):
            for j, y in enumerate(nums2):
                f[i + 1][j + 1] = max(max(f[i][j], 0) + x * y, f[i][j + 1], f[i + 1][j])
        return f[n][m]

###java

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[][] f = new int[n + 1][m + 1];
        for (int[] row : f) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f[i + 1][j + 1] = Math.max(
                    Math.max(f[i][j], 0) + nums1[i] * nums2[j],
                    Math.max(f[i][j + 1], f[i + 1][j])
                );
            }
        }
        return f[n][m];
    }
}

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        vector f(n + 1, vector<int>(m + 1, INT_MIN));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int res1 = max(f[i][j], 0) + nums1[i] * nums2[j];
                // 注：max({...}) 比 max(..., max(...)) 慢
                f[i + 1][j + 1] = max(res1, max(f[i][j + 1], f[i + 1][j]));
            }
        }
        return f[n][m];
    }
};

###go

func maxDotProduct(nums1, nums2 []int) int {
n := len(nums1)
m := len(nums2)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
for j := range f[i] {
f[i][j] = math.MinInt
}
}

for i, x := range nums1 {
for j, y := range nums2 {
f[i+1][j+1] = max(max(f[i][j], 0)+x*y, f[i][j+1], f[i+1][j])
}
}
return f[n][m]
}

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
• 空间复杂度：$\mathcal{O}(nm)$。

五、空间优化

类似 1143. 最长公共子序列 的空间优化方法，只用一个长为 $m+1$ 的一维数组，原理讲解请看 最长公共子序列 编辑距离【基础算法精讲 19】。

###py

# 更快的写法见【Python3 手写 max】
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums2)
        f = [-inf] * (m + 1)
        for x in nums1:
            pre = f[0]
            for j, y in enumerate(nums2):
                tmp = f[j + 1]
                f[j + 1] = max(max(pre, 0) + x * y, f[j + 1], f[j])
                pre = tmp
        return f[m]

###py

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums2)
        f = [-inf] * (m + 1)
        for x in nums1:
            pre = f[0]
            for j, y in enumerate(nums2):
                tmp = f[j + 1]
                res = x * y
                if pre > 0: res += pre
                if f[j] > res: res = f[j]
                if f[j + 1] > res: res = f[j + 1]
                f[j + 1] = res
                pre = tmp
        return f[m]

###java

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums2.length;
        int[] f = new int[m + 1];
        Arrays.fill(f, Integer.MIN_VALUE);
        for (int x : nums1) {
            int pre = f[0];
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                f[j + 1] = Math.max(Math.max(pre, 0) + x * nums2[j], Math.max(f[j + 1], f[j]));
                pre = tmp;
            }
        }
        return f[m];
    }
}

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int m = nums2.size();
        vector<int> f(m + 1, INT_MIN);
        for (int x : nums1) {
            int pre = f[0];
            for (int j = 0; j < m; j++) {
                int tmp = f[j + 1];
                f[j + 1] = max(max(pre, 0) + x * nums2[j], max(f[j + 1], f[j]));
                pre = tmp;
            }
        }
        return f[m];
    }
};

###go

func maxDotProduct(nums1, nums2 []int) int {
m := len(nums2)
f := make([]int, m+1)
for i := range f {
f[i] = math.MinInt
}
for _, x := range nums1 {
pre := f[0]
for j, y := range nums2 {
tmp := f[j+1]
f[j+1] = max(max(pre, 0)+x*y, f[j+1], f[j])
pre = tmp
}
}
return f[m]
}

复杂度分析

• 时间复杂度：$\mathcal{O}(nm)$，其中 $n$ 是 $\textit{nums}_1$ 的长度，$m$ 是 $\textit{nums}_2$ 的长度。
• 空间复杂度：$\mathcal{O}(m)$。

专题训练

见下面动态规划题单的「§4.1 最长公共子序列（LCS）」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

灵神dp题单打卡

思路

定义$dfs(i,j) $,代表了以前$i$和$j$个数中$nums1$和$nums2$最大点积
（即$nums1[0...i]$和$nums2[0...j]$的最大点积）。

• 如果选当前位置，那么算出当前位置点积为$nums1[i] * nums2[j]$，同时看前面位置的最大点积$dfs(i - 1,j - 1)$是否大于0，如果小于0的话，越加越小，不如不要，跟0取max就可以实现。状态方程如下：
  $$dfs(i,j) = max(dfs(i - 1,j - 1),0) + nums1[i] * nums2[j]$$
• 如果不选当前位置，也就是跳过一格，状态方程如下：
  $$dfs(i,j) = max(dfs(i - 1,j),dfs(i,j - 1))$$

递推是记忆化搜索1: 1翻译而来，而空间优化则是在二维的基础上，观察值如何转移的优化的。具体可见b站灵神算法精讲中的内容，有总结。

Code

###C++

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(),m = nums2.size();
        vector<vector<int>> memo(n,vector<int>(m,INT_MIN));
        function<int(int,int)> dfs = [&](int i,int j) -> int{
            if(i < 0 || j < 0) return INT_MIN;
            if(memo[i][j] != INT_MIN) return memo[i][j];
            //选
            memo[i][j] = max(dfs(i - 1,j - 1),0) + nums1[i] * nums2[j];
            memo[i][j] = max({memo[i][j],dfs(i - 1,j),dfs(i,j - 1)});
            return memo[i][j];
        };
        return dfs(n - 1,m - 1);
    }
};

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(),m = nums2.size();
        vector<vector<int>> memo(n,vector<int>(m,INT_MIN));
        //新一点的递归写法
        auto dfs = [&](this auto&& self,int i,int j) -> int{
            if(i < 0 || j < 0) return INT_MIN;
            if(memo[i][j] != INT_MIN) return memo[i][j];
            //选
            memo[i][j] = max(self(i - 1,j - 1),0) + nums1[i] * nums2[j];
            memo[i][j] = max({memo[i][j],self(i - 1,j),self(i,j - 1)});
            return memo[i][j];
        };
        return dfs(n - 1,m - 1);
    }
};

###c++

    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(),m = nums2.size();
        vector<vector<int>> f(n + 1,vector<int>(m + 1,INT_MIN));
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                f[i + 1][j + 1] = max({max(f[i][j],0) + nums1[i] * nums2[j],
                                    f[i + 1][j],f[i][j + 1]});
            }
        }
        return f[n][m];
    }

###c++

    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(),m = nums2.size();
        vector<int> f(m + 1,INT_MIN);
        for(int i = 0;i < n;i++){
            f[0] = INT_MIN;//这里相当于初始化第一列。
            int pre = INT_MIN;
            for(int j = 0;j < m;j++){
                int t = f[j + 1];
                f[j + 1] = max({max(pre,0) + nums1[i] * nums2[j],
                                    f[j],f[j + 1]});
                pre = t;
            }
        }
        return f[m];
    }

题意

本题就是求两个子序列点积的最大值。题意很明确，直接说解法。
很显然这题用dp做，但是状态转移方程怎么写，dp[i][j]代表什么意思，依然是一个值得写一下的问题。

首先我们考虑dp[i][j]代表什么意思。

dp[i][j]的含义

第一种想法：
dp[i][j]的含义是以nums1[i]和nums2[j]结尾的子序列的最大点积。
第二种想法：
dp[i][j]的含义是到nums1[i]和nums2[j]为止的子序列的最大点积。

这两种是不一样的：
第一种想法一定要包含nums1[i]和nums2[j]，因为以它们结尾。
但是第二种想法就没有这个限制，以谁结尾无所谓，最主要是大。

我们应该使用第二种，具体原因是因为状态转移方程。

状态转移方程

第一种想法的状态转移方程怎么写呢？

dp[i][j]=max(nums1[i]*nums2[j] , nums1[i]*nums2[j]+ maxVal);  

首先我们知道nums1[i]*nums2[j]这个值在第一种想法中是一定要有的。
接下来我们可以选择只有这两项或者包含前面的子序列点积最大值：
假如只有这两项，那么就什么都不加；假如也包含前面的就加上前面子序列点积的最大值maxVal。

来算一下时间复杂度：
首先算n^2个dp值
在每次dp计算中都要找到前面子序列点积的最大值，又要花费n^2的时间
所以时间复杂度为n^4,(500)^4是超时的

第二种想法的状态转移方程怎么写呢？
第二种可以选择nums1[i]和nums2[j]，所以我们可以通过这个来写状态转移方程：
(其实对于子序列的很多dp题来讲，都可以使用选不选来写状态转移方程)

1.选择nums1[i]和nums2[j]

1.1不选择前面的 dp[i][j]=nums1[i]*nums2[j]
1.2也选择前面的 dp[i][j]=max(dp[i][j],nums1[i]*nums2[j]+dp[i-1][j-1])
因为dp[i][j]是截止到nums1[i]和nums2[j]中的最大点积，所以只需要dp[i-1][j-1]就可以了  
事实上从这里可以看出想法一就是想法二的情况之一

2.选择nums1[i],不选择nums2[j]

等价于dp[i][j-1]
dp[i][j]=max(dp[i][j],dp[i][j-1])

3.不选择nums1[i],选择nums2[j]

等价于dp[i-1][j]
dp[i][j]=max(dp[i][j],dp[i-1][j])

4.？？？

聪明的你肯定知道了
状态方程你来写吧:dp[i][j]=max(dp[i][j],???)

代码

###cpp

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int sz1=nums1.size(),sz2=nums2.size();
        vector<vector<int>> dp(sz1+1,vector<int>(sz2+1,-1e8));

        for(int i=1;i<=sz1;i++){
            for(int j=1;j<=sz2;j++){
                //1.1
                dp[i][j]=nums1[i-1]*nums2[j-1];
                //1.2
                dp[i][j]=max(dp[i][j],nums1[i-1]*nums2[j-1]+dp[i-1][j-1]);
                //2
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
                //3
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
                //4
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
            }
        }
        return dp[sz1][sz2];
    }
};

哦，对，求个赞

有疑问评论区可以交流，看到一定回

给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。

由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。

 

示例 1：

输入：root = [1,2,3,4,5,6]
输出：110
解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）

示例 2：

输入：root = [1,null,2,3,4,null,null,5,6]
输出：90
解释：移除红色的边，得到 2 棵子树，和分别是 15 和 6 。它们的乘积为 90 （15*6）

示例 3：

输入：root = [2,3,9,10,7,8,6,5,4,11,1]
输出：1025

示例 4：

输入：root = [1,1]
输出：1

 

提示：

• 每棵树最多有 50000 个节点，且至少有 2 个节点。
• 每个节点的值在 [1, 10000] 之间。