算法设计与分析复习03：动态规划算法

爱被打了一巴掌 2024-03-30 13:33 161阅读 0赞

> 作者：非妃是公主  
> 专栏：《算法》  
> **个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩**
> 
> ![在这里插入图片描述][7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]
> 
> ### 专栏系列文章 ###
> 
> [算法设计与分析复习01：主方法求递归算法时间复杂度][01]
> 
> [算法设计与分析复习02：分而治之算法][02]
> 
> [算法设计与分析复习03：动态规划算法][03]  
> [算法设计与分析复习04：贪心算法][04]
> 
> [算法设计与分析复习05：回溯及分支限界][05]
> 
> [算法设计与分析复习06：随机化算法][06]
> 
> [算法设计与分析复习07：样题][07]
> 
> #### 文章目录 ####
> 
>  *   *  专栏系列文章
>      *  复习重点
>      *  动态规划算法
>      *   *  斐波那契数列及其应用
>          *  矩阵链乘法+凸多边形剖分
>          *   *  矩阵链乘法
>              *  凸多边形剖分
>          *  最长公共子序列
>          *  最大子段和（字数组）
>          *  0-1背包
>          *  编辑距离
>          *  钢条切割

### 复习重点 ###

![在这里插入图片描述][16ee73d314d24fd7a218b4b65604a9f6.png]

### 动态规划算法 ###

#### 斐波那契数列及其应用 ####

递归方法实现斐波那契数列：  
![在这里插入图片描述][845e0b45ea59416f8f1902f6fd704bc8.png]  
n=5时，fib(5)的计算过程  
![在这里插入图片描述][b83b65ae9b6948e9b915d5a08a516a5d.png]

时间复杂度为 O ( 2 n ) O(2^n) O(2n)，随问题规模，呈指数级别增加。  
斐波那契数列：记忆化搜索实现，使用一个数组将重复的计算过程记录下来。  
![在这里插入图片描述][455ba85b9c70471686802c534de5b4cc.png]

记忆化搜索的时间复杂度为 O ( n ) O(n) O(n)。  
斐波那契数列：动态规划实现  
![在这里插入图片描述][105636cb773447a1939cacc5f265624c.png]

动态规划的时间复杂度也为 O ( n ) O(n) O(n)。  
不同之处在于，动态规划自底向上进行计算，记忆化搜索自顶向下计算  
![在这里插入图片描述][c04345dc30304d0c98f6e3d0aed15973.png]

#### 矩阵链乘法+凸多边形剖分 ####

##### 矩阵链乘法 #####

纯递归方法，根据动态转移方程：  
![在这里插入图片描述][d2c0239be7f14c07969c66ba3cb28c93.png]  
其中，`RecurMatrixChain(i, k, s, p)`为矩阵i到矩阵k所需要的最少数乘次数。

int RecurMatrixChain(int i, int j, int** s, int* p)
    {
        
    	if (i == j) return 0;
    	int u = INT_MAX;
    	for (int k = i; k < j; k++)
    	{
        
    		int t = RecurMatrixChain(i, k, s, p)
    			+ RecurMatrixChain(k + 1, j, s, p) + p[i - 1] * p[k] * p[j];
    		if (t < u)
    		{
        
    			u = t;
    			s[i][j] = k;
    		}
    	}
    	return u;
    }

直接递归中右大量重复计算：  
![在这里插入图片描述][bae9f787889945b68a518d7a7669e876.png]

消除重复计算的方法：MatrixChain运行举例  
![在这里插入图片描述][921abe92afea40cba5484e3e42f6021c.png]

通过一个 O ( n 2 ) O(n^2) O(n2)的表格进行记录，沿对角线进行计算。  
时间复杂度：  
 O ( n 3 ) O(n^3) O(n3)  
空间复杂度：  
 O ( n 2 ) O(n^2) O(n2)  
核心代码如下：

void MatrixChain(vector<int>& p, int n, vector<vector<int>>& m, vector<vector<int>>& s)
    {
        
    	for (int a = 1; a <= n; a++)
    		m[a][a] = 0;
    	for (int r = 2; r <= n; r++)
    		for (int i = 1; i <= n - r + 1; i++)
    		{
        
    			int j = i + r - 1;
    			m[i][j] = INT_MAX;
    			for (int k = i; k < j; k++)
    			{
        
    				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
    				if (t < m[i][j])
    				{
        
    					m[i][j] = t; s[i][j] = k;
    				}
    			}
    		}
    }

解追溯与测试代码如下：

int Traceback(int i, int j, vector<vector<int>> s) //找出s数组中记录的最优断开点
    {
        
    	if (i == j)
    		return -1;
    	Traceback(i, s[i][j], s);
    	Traceback(s[i][j] + 1, j, s);
    	cout << "包含矩阵A" << s[i][j];
    	cout << "的部分与包含矩阵A" << (s[i][j] + 1)
    		<< "的部分结合，放在一个括号中" << endl;
    	return 0;
    }
    
    int main() {
        
    	int n = 6;
    	vector<vector<int>> m(n + 1, vector<int>(n + 1));
    	vector<vector<int>> s(n + 1, vector<int>(n + 1));
    
    	vector<int> p(n + 1);
    	p = {
         5,10,3,12,5,50,6 };
    
    	MatrixChain(p, n, m, s);
    	for (int i = 0; i < n+1; i++) {
        
    		for (int j = 0; j < n+1; j++) {
        
    			cout << "\t" << m[i][j] << "\t";
    		}
    		cout << endl;
    	}
    	cout << endl;
    	for (int i = 0; i < n + 1; i++) {
        
    		for (int j = 0; j < n + 1; j++) {
        
    			cout << "\t" << s[i][j] << "\t";
    		}
    		cout << endl;
    	}
    	Traceback(1, n, s);
    }

##### 凸多边形剖分 #####

问题描述：  
![在这里插入图片描述][399c4e20862e447d9b1ed56b2ada39fa.png]

参考leetcode上题[leetcode1039：多边形三角剖分的最低得分][leetcode1039]  
![在这里插入图片描述][d529b9c9e6e548c882adab7c0169a7a5.png]  
其中，按照leetcode1039题目给出的权函数定义，所得最优子结构性质如下：  
 t \[ i \] \[ j \] = \{ 0 j - i <= 1 t \[ i \] \[ k \] + t \[ k \] \[ j \] + v a l u e s \[ i \] × v a l u e s \[ k \] × v a l u e s \[ j \] j- i > 1 t\[i\]\[j\]=\\left\\\{ \\begin\{matrix\} 0& \\text\{j - i <= 1\} \\\\ t\[i\]\[k\]+t\[k\]\[j\]+values\[i\]\\times\{values\[k\]\}\\times\{values\[j\]\}& \\text\{ j- i > 1\} \\end\{matrix\} \\right. t\[i\]\[j\]=\{ 0t\[i\]\[k\]\+t\[k\]\[j\]\+values\[i\]×values\[k\]×values\[j\]j - i <= 1 j- i > 1  
leetcode1039题解如下：

class Solution {
        
    public:
        int minScoreTriangulation(vector<int>& values) {
        
            int n = values.size();
            vector<vector<int>> dp(n, vector<int>(n));
            /*for (int i = 0; i < n; i++) {
                dp[i][i + 1] = 0;
            }*/
            for (int r = 3; r <= n; r++) //r为当前计算的链长（子问题规模）
            {
        
                for (int i = 0; i <= n - r; i++) //n-r+1为最后一个r链的前边界
                {
        
                    int j = i + r - 1;  //计算前边界为i，链长为r的链的后边界
                    dp[i][j] = INT_MAX; //将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=i
                    //s[i][j] = i;
                    for (int k = i + 1; k < j; k++) {
        
                        //将链ij划分为( A[i:k] )* (A[k+1:j])
                        int u = dp[i][k] + dp[k][j] + 
                            values[i] * values[k] * values[j];
                        if (u < dp[i][j]) {
        
                            dp[i][j] = u;
                            //s[i][j] = k;
                        }
                    }
                }
            }
            return dp[0][n-1];
        }
    };
    // 测试用例
    int main() {
        
        Solution solution;
        vector<int>values = {
         3,7,4,5 };
        int n = solution.minScoreTriangulation(values);
        cout << n;
    }

#### 最长公共子序列 ####

![在这里插入图片描述][7a3822b61f7e4e9799638289abb3f58e.png]  
![在这里插入图片描述][5049bec44cfc47dda3e43cf2aab77fab.png]  
最优子结构性质：  
![在这里插入图片描述][5c8933d7b3af4d6d8a9b54d8fd7f5b4c.png]  
填表过程：  
![在这里插入图片描述][2fb381ce00e2422e9f29a2eedfc0b201.png]  
![在这里插入图片描述][a514d19cd4ff4ae49fd36e13e5282018.png]

![在这里插入图片描述][97988e171bc54cd68c13b84cf8b995bf.png]  
![在这里插入图片描述][e2d2766ebe8049c7ae7314e9901e9d95.png]  
核心代码：

#include<string>
    #include<vector>
    #include<iostream>
    using namespace std;
    class Solution {
        
    public:
        int longestCommonSubsequence(string text1, string text2) {
        
            int m = text1.size();
            int n = text2.size();
            vector<vector<int>>C(m + 1, vector<int>(n + 1));
            vector<vector<int>>rec(m + 1, vector<int>(n + 1));
            for (int i = 1; i < m + 1; i++) {
        
                for (int j = 1; j < n + 1; j++) {
        
                    if (text1[i - 1] == text2[j - 1]) {
        
                        C[i][j] = C[i - 1][j - 1] + 1;
                        rec[i][j] = 1;
                    }
                    else if (C[i][j - 1] > C[i - 1][j]) {
        
                        C[i][j] = C[i][j - 1];
                        rec[i][j] = 2;
                    }
                    else {
        
                        C[i][j] = C[i - 1][j];
                        rec[i][j] = 3;
                    }
                }
            }
            int i = m;
            int j = n;
            while (i > 0 && j > 0) {
        
                if (rec[i][j] == 1) {
         
                    cout << text1[i - 1]; 
                    i--;
                    j--;
                }
                else if (rec[i][j] == 2) {
        
                    j--;
                }
                else {
        
                    i--;
                }
            }
            return C[m][n];
        }
    };
    
    int main() {
        
        string text1 = "ybl";
        string text2 = "yby";
        Solution solution;
        int num = solution.longestCommonSubsequence(text1, text2);
        cout << endl << num;
    }

#### 最大子段和（字数组） ####

![在这里插入图片描述][c914eb301f174a7ca0cceb3e5d43d935.png]  
状态转移方程：  
 m a x v a l u e \[ i \] = \{ m a x v a l u e \[ i − 1 \] + n u m \[ i \] maxvalue\[i-1\] + num\[i\] > maxvalue\[i-1\] m a x v a l u e \[ i − 1 \] maxvalue\[i-1\] + num\[i\] < maxvalue\[i-1\] maxvalue\[i\]=\\left\\\{ \\begin\{matrix\} maxvalue\[i-1\] + num\[i\]& \\text\{ maxvalue\[i-1\] + num\[i\] > maxvalue\[i-1\] \} \\\\ maxvalue\[i-1\] & \\text\{ maxvalue\[i-1\] + num\[i\] < maxvalue\[i-1\] \} \\end\{matrix\} \\right. maxvalue\[i\]=\{ maxvalue\[i−1\]\+num\[i\]maxvalue\[i−1\] maxvalue\[i-1\] + num\[i\] > maxvalue\[i-1\]  maxvalue\[i-1\] + num\[i\] < maxvalue\[i-1\]

//方法1：
    class Solution {
        
    public:
        int maxSubArray(vector<int>& nums) {
        
            int pre = 0;
            int maxvalue = INT_MIN;
            for (auto num : nums) {
        
                pre = max(pre + num, num);
                maxvalue = max(maxvalue, pre);
            }
            return maxvalue;
        }
    };

#### 0-1背包 ####

问题描述：  
![在这里插入图片描述][2fdcc68afeba415fb107479ecf4d9c95.png]  
状态转移方程：  
 K n a p s a c k S R ( h , i , C ) = m a x ( K n a p s a c k S R ( h , i − 1 , C ) ， K n a p s a c k S R ( h , i − 1 , C − V \[ i \] ) + P \[ i \] ) KnapsackSR(h,i,C)=max(KnapsackSR(h,i-1,C)，KnapsackSR(h,i-1,C-V\[i\])+P\[i\]) KnapsackSR(h,i,C)=max(KnapsackSR(h,i−1,C)，KnapsackSR(h,i−1,C−V\[i\])\+P\[i\])  
递归求解：  
![在这里插入图片描述][ad910ab3b9b049029db7ffd5af1f9a33.png]  
![在这里插入图片描述][6211cbe499214a4c91225ab54153351b.png]  
dp求解（填表）：  
![在这里插入图片描述][ba2dd1cb06454862ae2345a487d272f6.png]  
![在这里插入图片描述][9dcd18dbfc174487960e1df7cddcfbc6.png]  
[leetcode416：分割和子集（和0-1背包问题）][leetcode416_0-1]核心代码：

#include<vector>
    #include<iostream>
    using namespace std;
    class Solution {
        
    public:
        bool canPartition(vector<int>& nums) {
        
            int sum = 0;
            for (auto num : nums) {
        
                sum += num;
            }
            if (sum % 2)return false;
            int C = sum / 2;
            vector<vector<int>> dp(nums.size(), vector<int>(C + 1));
            for (int i = 0; i < nums.size(); i++) {
        
                for (int j = 1; j < dp[0].size(); j++) {
        
                    if (i == 0) {
        
                        dp[i][j] = nums[i] > j ? 0 : nums[i];
                    }
                    else if (j < nums[i])
                        dp[i][j] = dp[i - 1][j];
                    else
                        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }
                if (dp[i][dp[0].size() - 1] == C)return true;
            }
            return false;
        }
    };
    
    int main() {
        
        vector<int> nums = {
         1,2,5 };
        Solution solution;
        cout << solution.canPartition(nums);
    }

#### 编辑距离 ####

问题描述：  
![在这里插入图片描述][7321e0dcfade423d82223557139b08a9.png]  
删除：  
![在这里插入图片描述][5bfb9b184f7e4bfd818af5e4457f21da.png]  
插入：  
![在这里插入图片描述][9c1b32f3d2c54f65ab222a9e97bf0055.png]  
替换：  
![在这里插入图片描述][3f9bfd829c80420e8632e75920eec3f4.png]  
![在这里插入图片描述][253b64185ba6457a97f56511514b95bf.png]  
填表：  
![在这里插入图片描述][a5b2315d2f9d4e2eb179d1c1ed89af5f.png]  
![在这里插入图片描述][dad0e16168044483b56e3ef34c8f36ef.png]![在这里插入图片描述][2c2301b24f2842449cd4c4c1c2c7875f.png]  
![在这里插入图片描述][4dd23f0cd4ac4c38b38e64ca8cddb5a7.png]  
![在这里插入图片描述][5894ac0abccb453ebb533c60cb55f921.png]  
![在这里插入图片描述][05ba1db4c7a54ca490f7b13a24148cb1.png]  
![在这里插入图片描述][5771bb6642c44083985bbcfeaedd0d80.png]  
追溯解：  
![在这里插入图片描述][ff2ad0b16a284aea9fd016a1a7e748f2.png]  
[leetcode72：编辑距离][leetcode72]核心代码：

#include<string>
    #include<vector>
    #include<iostream>
    using namespace std;
    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));
            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] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),
                            dp[i - 1][j - 1] + 1);
                    }
                }
            }
            return dp[m - 1][n - 1];
        }
    };
    
    int main() {
        
        string s1 = "horse";
        string s2 = "ros";
        Solution solution;
        int res = solution.minDistance(s1, s2);
        cout << res;
        return 0;
    }

#### 钢条切割 ####

状态转移方程：  
![在这里插入图片描述][70883c4a103c46349f84a3ffb21725ee.png]  
![在这里插入图片描述][2b515a63c4e540d09fd65fa5748a7c04.png]

#include<vector>
    #include<iostream>
    using namespace std;
    
    int CutFe(vector<int>p, int n) {
        
    	vector<int>C(n + 1);
    	for (int i = 0; i < n + 1; i++) {
        
    		int t = i - p.size() + 1;
    		for (int j = max(t, 0); j < i; j++) {
        //i-p.size()+1
    			C[i] = max(C[i], C[j] + p[i - j]);
    		}
    	}
    	return C[n];
    }
    int main() {
        
    	vector<int> p = {
         0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 24 };	
    	cout << CutFe(p, 10);
    	return 0;
    }

[7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2f82b6d69b7845c8a2031fbd11093e29.jpeg
[01]: https://blog.csdn.net/myf_666/article/details/128509102
[02]: https://blog.csdn.net/myf_666/article/details/128509126
[03]: https://blog.csdn.net/myf_666/article/details/128509143
[04]: https://blog.csdn.net/myf_666/article/details/128509159
[05]: https://blog.csdn.net/myf_666/article/details/128509168
[06]: https://blog.csdn.net/myf_666/article/details/128509174
[07]: https://blog.csdn.net/myf_666/article/details/128509183
[16ee73d314d24fd7a218b4b65604a9f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/862fa2abd50d49d5955c814bfcdd689c.png
[845e0b45ea59416f8f1902f6fd704bc8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e8dde28261f04e1d91c1aaf4ce51df0e.png
[b83b65ae9b6948e9b915d5a08a516a5d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9374a69bc75d44d78cb5599c4958dfe3.png
[455ba85b9c70471686802c534de5b4cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3f7fa0c9321543729b4bf54ba4c0d7c2.png
[105636cb773447a1939cacc5f265624c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1a911c2c2ccf41d6b019241cb5dc78b2.png
[c04345dc30304d0c98f6e3d0aed15973.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ce51a1725a4148cf9f0913d9c4eee154.png
[d2c0239be7f14c07969c66ba3cb28c93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/88599aa547f94448b5a5168675a70c9e.png
[bae9f787889945b68a518d7a7669e876.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a223a743c08544dd90a765cf81c71737.png
[921abe92afea40cba5484e3e42f6021c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f6274e11fa83410c98b5804a13ecd165.png
[399c4e20862e447d9b1ed56b2ada39fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/454950a9732c404b9460b1f018bfef7e.png
[leetcode1039]: https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/submissions/
[d529b9c9e6e548c882adab7c0169a7a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0e3711539e8a413d852bc2b0ffa25f69.png
[7a3822b61f7e4e9799638289abb3f58e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7b8570eb1a00465f910a92259cf92728.png
[5049bec44cfc47dda3e43cf2aab77fab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b0e7808df36c46c7a37b59a07d86d18d.png
[5c8933d7b3af4d6d8a9b54d8fd7f5b4c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b21cbf80d8ba4cbbbde617a61c949a3d.png
[2fb381ce00e2422e9f29a2eedfc0b201.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/38c22eec775347a2bc612feb2e0418c0.png
[a514d19cd4ff4ae49fd36e13e5282018.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/cdfd70826aab4f5092f9ad63bd4cc2e3.png
[97988e171bc54cd68c13b84cf8b995bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1f6a1a6f764a46b2a33c06cc4a2c01cb.png
[e2d2766ebe8049c7ae7314e9901e9d95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dbbd758f89c5418cb9d7fe4f4dcca80c.png
[c914eb301f174a7ca0cceb3e5d43d935.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/561a75938ed84293989bc283bdca4ee5.png
[2fdcc68afeba415fb107479ecf4d9c95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b38ac862be8b438e9289750190ebb8dc.png
[ad910ab3b9b049029db7ffd5af1f9a33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f941d8ff9f944f8f89b4b41d11f23f47.png
[6211cbe499214a4c91225ab54153351b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a8cdc3b0342243beb0866222f8f6e248.png
[ba2dd1cb06454862ae2345a487d272f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7c9c70731ae04a418aed7645c2cb04f9.png
[9dcd18dbfc174487960e1df7cddcfbc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/645a6499ac46464399b7546313edc1ca.png
[leetcode416_0-1]: https://leetcode-cn.com/problems/partition-equal-subset-sum/
[7321e0dcfade423d82223557139b08a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f5c99cc8ffe14e4a852f195eb9a3f373.png
[5bfb9b184f7e4bfd818af5e4457f21da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d96a3ec5aa9e4191ba7586023a2d04d0.png
[9c1b32f3d2c54f65ab222a9e97bf0055.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/16c5a088599349cd88a03a4e0a5b8cb1.png
[3f9bfd829c80420e8632e75920eec3f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f8555a776937444780f6f1928f37d8dc.png
[253b64185ba6457a97f56511514b95bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/586a688c817047f4b74f7383dbf69d2f.png
[a5b2315d2f9d4e2eb179d1c1ed89af5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/84db383e210e4bab8bdff1c2fffbedac.png
[dad0e16168044483b56e3ef34c8f36ef.png]: https://img-blog.csdnimg.cn/dad0e16168044483b56e3ef34c8f36ef.png
[2c2301b24f2842449cd4c4c1c2c7875f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1fc693fb46954b6b953a571a6401e2a6.png
[4dd23f0cd4ac4c38b38e64ca8cddb5a7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7d9a474954a648f1b1f367b1b65f812a.png
[5894ac0abccb453ebb533c60cb55f921.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/865470bdd7c94b4dab131e576c09eba4.png
[05ba1db4c7a54ca490f7b13a24148cb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0cdaac06bc4048c798c106ba742de038.png
[5771bb6642c44083985bbcfeaedd0d80.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/df5a5c15cbc34ea39e95d7c0ddc1331d.png
[ff2ad0b16a284aea9fd016a1a7e748f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d1946a56fc03418e945c3c506f295ecf.png
[leetcode72]: https://leetcode-cn.com/problems/edit-distance/
[70883c4a103c46349f84a3ffb21725ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ae5392d74e42440f89c51268ed3e28d3.png
[2b515a63c4e540d09fd65fa5748a7c04.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1340d75e9e734d079dc8dc7754aea359.png