https://leetcode.cn/problems/maximal-square/?envType=study-plan-v2&envId=top-interview-150
最大正方形 

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();   

        int max_len = 0;//记录最大边长
        vector<vector<int>> dp(m,vector<int>(n,0));
        // 初始化
        for(int i = 0; i < m; ++i)
        {
            if(matrix[i][0] == '1')
            {
                dp[i][0] = 1;
                max_len = max(max_len, dp[i][0]);
            }
        }
        for(int j = 0; j < n; ++j)
        {
            if(matrix[0][j] == '1')
            {
                dp[0][j] = 1;
                max_len = max(max_len, dp[0][j]);
            }
        }
        // 填表
        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                if(matrix[i][j] == '1')
                {
                    dp[i][j] = 1+min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                    max_len = max(max_len, dp[i][j]);
                }
            }
        }

        return max_len*max_len;
    }

};
// 思路：求最大正方形的面积，可以转换为求最大正方形的边长
// 以(i,j)位置为正方形的右下角
// 最大边长 = min(i上面有多少个连续的1，i左边有多少个连续的1，i的左上角有多少个连续的1)

// 状态表示：dp[i][j]表示以(i,j)位置为右下角的正方形的最大边长
// 状态转移方程：dp[i][j] = 1+min(dp[i-1][j],dp[i][j-1]);
// 边界问题：dp[0][j] = matrix[0][j]; dp[i][0] = matrix[i][0];
----------------------------------------------------------------------------------------------------
https://leetcode.cn/problems/edit-distance/?envType=study-plan-v2&envId=top-interview-150
编辑距离 

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size()+1;
        int n = word2.size()+1;

        vector<vector<int>> dp(m,vector<int>(n,0)); // 多开一行一列
        // 初始化（第一行中除了第一个位置，其余位置全为0）
        for(int i = 0; i < m; ++i)
        {
            dp[i][0] = i;
        }
        for(int j = 0; j < n; ++j)
        {
            dp[0][j] = j;
        }

        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                if(word1[i-1] == word2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = 1+min(dp[i][j-1],min(dp[i-1][j],dp[i-1][j-1]));
                }
            }
        }

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

// 思路：字符串的dp问题，根据最后一个位置划分情况
// 状态表示：dp[i][j]表示word1的前i个转化为word2的前j个字符所需要的最小操作次数
// 状态转移方程：
// word1[i] == word2[j] dp[i][j] = 1+dp[i-1][j-1];
// word1[i] != word2[j] dp[i][j] = 1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]);