📕1.位运算

1.1 二进制求和

/*  
    11
     1
  -----
   100
     直接从最后一位开始加，记得算完要翻转
     ！！最后的时候需要看一下进位，如果有进位的话，还需要补一位
*/
class Solution {
public:
    string addBinary(string a, string b) {
        int jin = 0;
        string ans = "";
        for(int i = a.size()-1,j=b.size()-1; i>=0||j>=0; i--,j--){
            int cur = jin;
            if(i >= 0) cur += a[i] - '0';//字母转数字
            if(j >= 0) cur += b[j] - '0';
            ans += (cur%2 + '0'); //数字转字母
            jin = cur/2;
        }
        if(jin) ans += '1'; //这里需要注意
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

1.2 颠倒二进制位

/* 
    法1:模拟过程
    先获得二进制表达，然后再转为十进制
*/
class Solution {
public:
    int reverseBits(int n) {
    //    string str(32, '1');
        string binary = "";
        for(int i = 31; i >= 0; i--){
            int cur = n%2;
            binary+=(cur+'0');
            n = n/2;
        }
        //上面获得的二进制就是反的
        int ans = 0;
        long long num = 1;
        for(int i = 31; i>=0; i--){
            ans = ans +  (binary[i]-'0')*num;
            num *= 2;
        }
        return ans;
    }
};

法2:位运算的性质

// 法2:位运算
class Solution {
public:
    int reverseBits(int n) {
        int ans = 0;
        for(int i = 0; i < 32 && n > 0; i++){
            //获得最右边的然后移到左边
            ans |= (n & 1) << (31-i);
            n>>=1;
        }
        return ans;
    }
};

法3:分治（想不到☁️）

// 法2:位运算
// 时间复杂度：O(logn)。
// 空间复杂度：O(1)。
/*
    uint32_t 是无符号的，它 没有负数，因此它的 范围更大，因为没有一位用来表示符号。
    32 位 uint32_t 的取值范围是：0 ～ 4,294,967,295（2^32 - 1）
    int: -2^31）～ 2,147,483,647（2^31 - 1） /-2,147,483,648 ～ 
*/
class Solution {
public:
    int M1 = 0x55555555; // 01010101010101010101010101010101
    int M2 = 0x33333333; // 00110011001100110011001100110011
    int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    int M8 = 0x00ff00ff; // 00000000111111110000000011111111
    int reverseBits(long long n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};

1.3 位1的个数

小技巧：

获取最后一个1:int last_one = n & -n;
清除 整数 n 中 最低位的 1，并且 保留其他位不变： n & (n - 1);
12; // 二进制：1100
获取最后一个1: 输出 4（二进制：0100）
只保留最后一个1: 输出 8（二进制：1000）

/*
    位运算判断每一位
*/
class Solution {
public:
    int hammingWeight(int n) {
        int ans = 0;
        while(n != 0){
            ans += (n&1)?1:0; //最后一位是1就加1
            // if(cur == 1) ans++;
            n = n >> 1; //右移1位
        }
        return ans;
    }
};

法2:位运算优化

/*
    时间复杂度：O(logn)。循环次数等于 n 的二进制位中 1 的个数
    n &(n-1):清除n中最低位的1
    位运算判断每一位
*/
class Solution {
public:
    int hammingWeight(int n) {
        int ans = 0;
        while(n != 0){
            n = n &(n-1);
            ans++;
        }
        return ans;
    }
};

1.4 只出现一次的数字

法1：位运算^

/*
    法1：位运算^：相同的为0，最后即为单个的数
    时间复杂度:o(N)
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = nums[0];
        for(int i = 1; i < nums.size();i++){
            ans ^= nums[i];
        }
        return ans;
    }
};

1.5 只出现一次的数字II

/*
    法1:哈希表
    时间复杂度：O(n)
    空间复杂度：O(n) [n/3+1] 空间复杂度不满足o(1)
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> mp;
        for(int num: nums){
            mp[num]++;
        }
        int ans = 0;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            if(it->second == 1){
                ans = it->first;
            }
        }
        return ans;
    }
};

1.6 数字范围按位与（思维/公共前缀）

n &(n-1):清除n中最低位的1

/*
    妙哉
    对所有数字按位与的结果就是对应二进制字符串的公共前缀和再用0补上后面的位数即可

*/
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int comm = 0;
        //公共前缀
        while(left < right){
            left >>= 1;
            right >>= 1;
            comm++;
        }
        return left << comm;
        
    }
};

/*
    妙哉
    对所有数字按位与的结果就是对应二进制字符串的公共前缀和再用0补上后面的位数即可

*/

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        //法1: 位移
        // 时间复杂度：O(N) 
        // int comm = 0;
        // //公共前缀
        // while(left < right){
        //     left >>= 1;
        //     right >>= 1;
        //     comm++;
        // }
        // return left << comm;

        /*
        法2:Brian Kernighan 算法
        用于清除二进制串中最右边的1
        */
        while(left < right){
            right &= right-1;
        }
        return right;
    }
};

🖊️2.数学

2.1 回文数

法1:

class Solution {
public:
    bool isPalindrome(int x) {
        int xx = x; //注意备份x
        if(x < 0) return false;
        long long num = 0;
        while(x){
            num = num*10 + x%10;
            x/=10;
        }
        return num == xx;
    }
};

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0 || (x%10==0 && x != 0)) return false;
        string s = "";
        while(x){
            s += x%10 + '0';
            x/=10;
        }
        string t = s;
        reverse(t.begin(), t.end());
        return s == t;
    }
};

2.2 加1

法1:模拟加法过程

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int jin = 1;
        int n = digits.size();
        for(int i = n - 1; i >= 0; i--){
            int cur = (digits[i] + jin)%10;
            jin = (digits[i] + jin)/10;
            digits[i] = cur;
        }
        if(jin) digits.insert(digits.begin(), jin); 
        return digits;
    }
};

法2:从后往前找第一个不为9的位🍭

/*
法2:官解：只需要关注末尾出现了几个9即可
        1）末尾没有9，直接将末尾的数+1
        2）有9.那么就是将第一个不为9的位置加1，然后后面全置为0
        3）全为9，那么就在前面多加一个1
*/
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        //不全是9
        for(int i = n - 1; i >= 0; i--){
            if(digits[i] != 9){
                digits[i]++;
                for(int j = i+1; j < n; j++){
                    digits[j] = 0;
                }
                return digits;
            }
        }
        //全是9
        vector<int> ans(n+1);
        ans[0] = 1;
        return ans;
    }
};

2.3 阶乘后的零

/*
    法1:数学
    0即为10个个数，也就是2*5，求2的个数和5的个数的最小值即可
    但是5的个数不会大于2的个数，所以可以只考虑5的个数
    时间复杂度：O(n)
*/
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int num = i;
            while(num%5 == 0){
                ans ++;
                num/=5;
            }
        }       
        return ans;
    }
};

法2:

/*
    法1:数学
    0即为10个个数，也就是2*5，求2的个数和5的个数的最小值即可
    但是5的个数不会大于2的个数，所以可以只考虑5的个数
*/
class Solution {
public:
    int trailingZeroes(int n) {
        int ans = 0;
        while(n){
            n /= 5;
            ans += n;
        }
        return ans;
    }
};

2.4 x的平方根

/* 
    法1:二分
*/


class Solution {
public:
    int mySqrt(int x) {
        //小于等于的最后一个
        int l = 0, r = x;
        int res = -1;
        while(l <= r){
            long long mid = l + (r-l)/2; //注意数据范围
            if((long long)mid*mid <= x){
                res = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return res;
    }
};

法2，牛顿迭代法？

2.5 pow(x,n)

/*  
    快速幂,时间复杂度：o(N)
*/
class Solution {
public:
    double ksm(double a,long long b){
        double ans = 1, base = a;
        while(b != 0){
            if(b&1!=0) ans*=base;
            base *= base;
            b>>=1; //b=b/2; 
            // 注意数据类型 -231 <= n <= 231-1  -231加完负号就超出int了
        }
        return ans;
    }
    double myPow(double x, long long n) {
        if(n>0) return ksm(x,n);
        else return 1.0/ksm(x,-n);
    }
};

2.6 直线上最多的点数（枚举+哈希）

法1:暴力（可恶，竟然没想到）

/*
    暴力
    时间复杂度o(n3) 竟然可以过
*/
class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if(n <= 2) return n;
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                int cnt = 2;
                for(int k = j + 1; k < n; k++){
                    int x1 = points[i][0], y1 = points[i][1];
                    int x2 = points[j][0], y2 = points[j][1];
                    int x3 = points[k][0], y3 = points[k][1];
                    if((y3-y2)*(x2-x1) == (y2-y1)*(x3-x2)) cnt++;
                }
                res = max(res,cnt);
            }
        }
        return res;
    }
};

法2:枚举+哈希表统计

/*
    枚举+哈希统计
    时间复杂度：o(n2)
    以每个点为基准点，统计从i出发，与其他点j所形成的直线的斜率出现的次数
    注意：
    1）斜率不可以用浮点数表示（存在精度问题）=》采用约分后的方向向量（需要求最大公约数）
    2）还有符号问题，比如2/-1 和 -2/1其实是一样的， 我们保证让dx>0，有负号就加到dy
    3）对于竖直直线，统一为（0，1）
        对于水平线，统一为（1，0）


*/
class Solution {
public:
    int gcd(int a,int b){
        if(b == 0) return a;
        return gcd(b,a%b);
    }
    int lcm(int a,int b){
        return a*b/gcd(a,b);
    }

    int maxPoints(vector<vector<int>>& points) {
        int n = (int)points.size();
        if (n <= 2) return n;
        int ans = 1;

        for (int i = 0; i < n; i++) {
            map<pair<int,int>, int> mp;
            int best = 0;
            int x1 = points[i][0], y1 = points[i][1];
            for (int j = i + 1; j < n; j++) {
                int x2 = points[j][0], y2 = points[j][1];
                int dx = x2 - x1;
                int dy = y2 - y1;
                if (dx == 0) dy = 1; // 统一为 (0, 1)
                else if (dy == 0) dx = 1; // 统一为 (1, 0)
                else {
                    int g = gcd(abs(dx), abs(dy));
                    dx /= g; dy /= g;
                    // 统一符号：保证 dx > 0
                    if (dx < 0) {
                        dx = -dx;
                        dy = -dy;
                    }
                }
                pair<int,int> key = {dx, dy};
                int cur = ++mp[key];
                best = max(best, cur);
            }
            ans = max(ans, best + 1);
        }
        return ans;
    }
};

💌 3.一维动态规划

3.1 爬楼梯

法1:记忆化搜索

class Solution {
public:
    long long f[50];
    long long dfs(int n) {
        if (f[n] != 0)
            return f[n];
        if (n == 1) return f[1] = 1;
        if (n == 2) return f[2] = 2;
        return f[n] = dfs(n-1) + dfs(n-2);
    }
    int climbStairs(int n) {
        long long ans = dfs(n);
        return ans;
    }
};

法2:动态规划

//动态规划
class Solution {
public:
    long long dp[50];
    int climbStairs(int n) {
        dp[1] = 1, dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

3.2 打家劫舍

/*
    dp[i]:前i个房间能偷窃的最大总金额
    转移方程：
    dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    偷前k-1间房子，现在不偷； 偷前k-2和k
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0], nums[1]);
        vector<int> dp(n, 0);
        dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; i++){
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[n-1];
    }
};

3.3 单词拆分

法1:暴力(tle)

// dfs:tle
class Solution {
public:
    bool dfs(string cur,string& s,vector<string>& wordDict){
        if(cur.size() >= s.size()){
            if(cur==s) return true;
            return false;
        }
        bool ok = false;
        for(int i = 0; i < wordDict.size(); i++){
            ok |= dfs(cur+wordDict[i], s, wordDict);
        }
        return ok;

    }
    bool wordBreak(string s, vector<string>& wordDict) {
        return dfs("",s,wordDict);
    }
};

法2:dfs+剪枝

// dfs:tle
class Solution {
public:
    unordered_map<string,bool> map;
    bool dfs(string cur,string& s,vector<string>& wordDict){
        if(map.find(cur) != map.end()) return map[cur];
        if(cur.size() >= s.size()){
            if(cur==s) return true;
            return false;
        }
        bool ok = false;
        for(int i = 0; i < wordDict.size(); i++){
            string t = cur+wordDict[i];
            if( t== s.substr(0,t.size()))
                ok |= dfs(t, s, wordDict);
        }
        map[cur] = ok;
        return ok;

    }
    bool wordBreak(string s, vector<string>& wordDict) {
        return dfs("",s,wordDict);
    }
};

法3：动态规划

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        unordered_set<string> wordSet;
        for(string word: wordDict) wordSet.insert(word);
        vector<bool> dp(n + 1, false); // dp[i] 表示 s[0..i-1] 是否能被拆分
        dp[0] = true; // 空字符

        for (int i = 1; i <= n; ++i) {
            // 遍历前面所有可能的 j，检查 s[j..i-1] 是否是字典中的单词
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordSet.find(s.substr(j, i - j)) != wordSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n]; 
    }
};

3.4 零钱兑换

/*
    定义dp[i]为组成i需要的最少硬币数

*/
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<long long> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.size(); j++){
                if(coins[j] <= i){
                    dp[i] = min(dp[i],dp[i-coins[j]] + 1);
                }
            }
        }
        if(dp[amount] >= INT_MAX) return -1;
        return dp[amount]; 
    }
};

3.5 最长上升子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i],dp[j] + 1);
            }
        }
        int ans = 1;
        for(int i = 0; i < n; i++){
            ans = max(ans,dp[i]);
        }
        return ans;
        
    }
};

📒 4.多维动态规划

4.1三角形最小路径和

// 自底向上好像也不错 最后一行作为初始化，结果为dp[0][0];
// dp [i][j]:从顶点到（i,j）的最小路径和
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>>dp(n,vector<int>(n,1e8));
        dp[0][0] = triangle[0][0];

        for(int i = 1; i < triangle.size(); i++){
            for(int j = 0; j <= i; j++){
                if(j-1 >= 0)
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + triangle[i][j]);
                dp[i][j] = min(dp[i][j], dp[i-1][j] + triangle[i][j]);
            }
        }
        int minn = dp[n-1][0];
        for(int i = 0; i < triangle.size(); i++){
            minn = min(minn, dp[n-1][i]);
        }
        return minn;
    }
};

法2:自底向上计算

/*
    至底向上算
    
*/
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.back()); //用最后一行初始化
        for(int i = triangle.size() - 2; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = min(dp[j],dp[j+1]) + triangle[i][j];
            }
        }
        return dp[0];
    }
};

4.2 最小路径和

/*
    dp[i][j]:从原点到（i,j）的最小数字和
    时间复杂度：O(mn)
*/
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>>dp(n, vector<int>(m,1e8));
        dp[0][0] = grid[0][0];
        for(int i = 1; i < n; i++){
          dp[i][0] = dp[i-1][0] + grid[i][0];  
        }
        for(int j = 1; j < m ;j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j];
            }
        }
        return dp[n-1][m-1];
    }
};

4.3 不同路径II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>>dp(n, vector<int>(m,0));
        dp[0][0] = 1 - grid[0][0];  //注意这里
        for(int i = 1; i < n; i++){
            if(grid[i][0] == 1) dp[i][0] = 0;
            else dp[i][0] = dp[i-1][0];
        }
        for(int j = 1; j < m; j++){
            if(grid[0][j] == 1) dp[0][j] = 0;
            else dp[0][j] = dp[0][j-1];
        }

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
               if(grid[i][j] == 1) dp[i][j] = 0;
               else  dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[n-1][m-1];
    }
};

4.4 最长回文子串

动态规划，区间dp

// 区间dp
// dp[i][j]代表i-j是否为回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if(n < 2) return s;  //!!!
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++) dp[i][i] = 1;
        int st = 1, maxn = 1;
        for(int len = 2; len <= n; len++){
            for(int l = 0; l+len-1 < n ;l++){
                int r = l + len - 1;
                if(s[l] == s[r]){
                    if(dp[l+1][r-1] == 1 || (l+1)==r){
                        dp[l][r] = 1;
                        if(len > maxn){
                            maxn = len;
                            st = l;
                        }
                    }
                    
                }
            }
        }
    return s.substr(st, maxn);
    }
};

法2:中心扩散法：

// 中心扩散法
// 从每个位置出发，向两边扩散，遇到不是回文时结束！
class Solution {
public:
    int dp[1100][1100];
    string longestPalindrome(string s) {
        if(s.length() < 2) return s;
        int len = s.length();
        int max_len = 0;
        int st = 0;
        for(int i = 1; i < len; i++){
            int curmax = 1;
            int l = i, r = i;
            // 向左扩展
            while(l - 1 >= 0 && s[l - 1] == s[i]){
                l--;
                curmax++;
            }
            // 向右扩展
            while(r + 1 < len && s[r + 1] == s[i]){
                r++;
                curmax++;
            }
            while(l - 1 >= 0 && r + 1 < len && s[l-1] == s[r+1]){
                l--;
                r++;
                curmax += 2;
            }
            if(curmax > max_len){
                st = l;
                max_len = curmax;
            }
        }

        if(max_len == 0){
            return s[0] + "";
        }

        return s.substr(st, max_len);
    }
};

4.5 交错字符串

/*
    dp[i][j]：s1的 前i个元素和 s2的前j个元素是否组成s3的前i+j个字符
    1）如果s1 的第i个和s3的第i+j个元素相等
     取决于s1的前i-1个和s2的前j个 是否可以和 s3的前i+j-1个元素
    同时s1[i-1] == s3[i+j-1]
    =》dp[i-1][j] && (s1[i-1] == s3[i+j-1])
    2）如果s2 的第j个元素和s3的第i+j个元素相等
    取决于s2的前j-1个和s1的前i个 是否可以和 s3的前i+j-1个元素
    同时 s2[j-1] 必须等于 s3[i+j-1]
    =》dp[i][j-1] && (s2[j-1] == s3[i+j-1])

    时间复杂度： O(nm)
    空间复杂度： O(nm)
*/
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size();
        int m = s2.size();
        int q = s3.size();
        if((n+m) != q) return false;
        vector<vector<bool>> dp(n+1, vector<bool>(m+1,false));
        dp[0][0] = 1;
        // s1的前i个是否可以组成s3的前i个
        for (int i=1;i<=n;i++)
            dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1]);
        // s2的前j个是否可以组成s3的前j个
        for (int j=1;j<=m;j++)
            dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1]);
        //
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    dp[i][j] = (dp[i][j-1] && s2[j-1] == s3[i+j-1]) ||
                             (dp[i-1][j] && s1[i-1] == s3[i+j-1]);
                }
            }
        return dp[n][m];

    }
};

/*
    dp[j]:当前行 i 下的 dp[i][j]
    更新时：
        dp[j] 在更新前还是上一行的 dp[i-1][j]
        dp[j-1] 已经是当前行更新后的 dp[i][j-1]
*/
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = (int)s1.size();
        int m = (int)s2.size();
        if (n + m != (int)s3.size()) return false;

        // dp[j] 表示当前 i 行的 dp[i][j]
        vector<char> dp(m + 1, 0);

        // 初始化 i = 0：只用 s2 的前 j 个去匹配 s3 的前 j 个
        dp[0] = 1;
        for (int j = 1; j <= m; j++) {
            dp[j] = dp[j - 1] && (s2[j - 1] == s3[j - 1]);
        }

        for (int i = 1; i <= n; i++) {
            // 更新 dp[0]：只用 s1 的前 i 个去匹配 s3 的前 i 个
            dp[0] = dp[0] && (s1[i - 1] == s3[i - 1]);

            for (int j = 1; j <= m; j++) {
                dp[j] = (dp[j] && (s1[i - 1] == s3[i + j - 1])) || (dp[j - 1] && (s2[j - 1] == s3[i + j - 1]));
            }
        }

        return dp[m];
    }
};

4.6 编辑距离

/*
    dp[i][j]表示s1的前i个字符转换成s2的前j个字符需要的最少操作数
    
    对于字符串“xyz“和“xaz" 从最后一个字符开始比较，最后一个字符相等，所以比较前两个字符，即dp(i,j) = dp(i-1,j-1)
    下面是不相等的情况，xy. xa
    （1）增加，在s1 末尾a，xya,xa 此时末尾相同 转化为对比xy和 x即
        dp(i,j) = dp(i,j-1)+1
    （2）删除：删除末尾字符y，dp(xy,xa) = dp(x,xa)+1;
        dp(i,j) = dp(i-1,j) + 1
    (3)修改,修改y为a，dp(xy,xa) = dp(x,x)+1,即
        dp(i,j) = dp(i-1,j-1)+1
*/

class Solution {
public:
    int minDistance(string word1, string word2) {
        word1 = " " + word1; // 空串的除处理
        word2 = " " + word2;
        int n = word1.size();
        int m = word2.size();
        vector<vector<int>>dp(n,vector<int>(m));
        for(int i = 0; i < n; i++){
            dp[i][0] = i;
        }
        for(int i = 0; i < m; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(word1[i] == word2[j]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                }
            }
        }
        return dp[n-1][m-1];
    }
};

4.7 买卖股票的最佳时机III

class Solution {
public:
    int maxProfit(vector<int>& w) {
       int n = w.size();
       vector<array<array<long long,3>,2>> dp(2);
        // long long dp[n][2][3];
       dp[0][0][0] = 0; dp[0][0][1] = INT_MIN; dp[0][0][2] = INT_MIN;
       dp[0][1][0] = -w[0]; 
       dp[0][1][1] = INT_MIN; dp[0][1][2] = INT_MIN;

        long long ans = 0;
        for(int i = 1; i < n; i++){
            dp[i%2][0][0] = dp[(i-1)%2][0][0];
            dp[i%2][0][1] = max(dp[(i-1)%2][0][1],dp[(i-1)%2][1][0]+w[i]);
            dp[i%2][0][2] = max(dp[(i-1)%2][0][2], dp[(i-1)%2][1][1] + w[i]);

            // dp[i][1][0] = dp[i-1][0][0] - w[i];
            dp[i%2][1][0] = max(dp[(i-1)%2][1][0], dp[(i-1)%2][0][0] - w[i]);
            dp[i%2][1][1] = max(max(dp[(i-1)%2][1][1],dp[(i-1)%2][0][1]-w[i]),
                        dp[(i-1)%2][1][1]);
            dp[i%2][1][2] = max(max(dp[(i-1)%2][0][2],dp[(i-1)%2][0][2]-w[i]),dp[(i-1)%2][1][2]);
        }
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 3; j++){
                ans = max(ans,max(dp[i][0][j],dp[i][1][j]));
            }
        }
        return ans;

    }
};

4.8 买卖股票的最佳时机IV

class Solution {
public:
    int maxProfit(int k, vector<int>& w) {
       int n = w.size();
       if(n == 0) return 0;
        vector<vector<vector<long long>>> dp(2, vector<vector<long long>>(2, vector<long long>(k + 1, INT_MIN)));
        dp[0][0][0] = 0;
        dp[0][1][0] = - (long long)w[0];

        long long ans = 0;
        for(int i = 1; i < n; i++){
            dp[i%2][0][0] = dp[(i-1)%2][0][0];
            dp[i%2][1][0] = max(dp[(i-1)%2][1][0], dp[(i-1)%2][0][0] - (long long)w[i]);
            for(int t = 1; t <= k; t++){
                dp[i%2][0][t] = max(dp[(i-1)%2][0][t],dp[(i-1)%2][1][t-1]+w[i]);
                dp[i%2][1][t] = max(dp[(i-1)%2][1][t],dp[(i-1)%2][0][t]-w[i]);
            }
        }
        int last = (n - 1) % 2;
        for (int t = 0; t <= k; t++) {
            ans = max(ans, max(dp[last][0][t], dp[last][1][t]));
        }
        return ans;

    }
};

4.9 最大正方形（前缀和/dp）

法1:二维前缀和暴力

class Solution {
public:
    int rectSum(const vector<vector<int>>& sum, int x1, int y1, int x2, int y2) {
        return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
    }

    int maximalSquare(vector<vector<char>>& matrix) {
        int n = (int)matrix.size();
        if (n == 0) return 0;
        int m = matrix[0].size();
        if (m == 0) return 0;

        vector<vector<int>> sum(n + 1, vector<int>(m + 1, 0));
        // sum[i][j]表示前i行前j列的和
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (matrix[i - 1][j - 1] - '0');
            }
        }

        int maxn = 0;
        int len_max = min(n, m);

        for (int len = 1; len <= len_max; len++)                {                
            for (int x1 = 1; x1 + len - 1 <= n; x1++) {
                for (int y1 = 1; y1 + len - 1 <= m; y1++) {     
                    int x2 = x1 + len - 1;
                    int y2 = y1 + len - 1;                     
                    int temp = rectSum(sum, x1, y1, x2, y2);
                    if (temp == len * len) {             
                        maxn = max(maxn, len * len);        
                    }
                }
            }
        }
        return maxn;
    }
};

法2:dp

/*
    dp[i][j]：以(i,j)为右下角的正方形的最大边长，如果（i,j)为0，那么不存在全为1的正方形 dp[i][j] = 0,
              如果（i,j）为1，那么至少存在一个大小为1的正方形，然后看与其相邻的上面，左边，左上三个点的最小值（木桶原理）
                
*/
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        if(m == 0 || n == 0) return 0;
        int maxn = 0;
        vector<vector<int>> dp(n,vector<int>(m));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0) dp[i][j] = 1;
                    else dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    maxn = max(maxn,dp[i][j]);
                }

            }
        }
        return maxn*maxn;
    }
};