1. 知识点总结

题目	难度	知识点
爬楼梯	🐸	斐波那契
简化路径	🐸	字符串处理
编辑距离	🐸🐸🐸	DP蛮经典的题目

2. 分题题解

2.1 爬楼梯

无难度，其实也可以不开数组

class Solution {
public:
    int climbStairs(int n) {
        //FIB变式
        if(n<=2)return n;
        vector<int>dp(n+1);
        dp[1]=1;dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

2.2 简化路径

不是很难，注意细节，比如这个/不是对称的

class Solution {
public:
    string simplifyPath(string path) {
        vector<string>names;//存储各个节点的文件名
        int cnt=0;
        path+="/";
        string temp="";
        bool flag=false;
        for(int i=0;i<path.length();i++){
            if(path[i]=='/'){
               if(temp=="."){
                   //当前目录
               }else if(temp==".."){
                   if(cnt){
                       names.pop_back();
                       cnt--;
                   }
               }else if(temp!=""){
                   names.push_back(temp);
                   cnt++;
               }
               temp="";
            }else{
                temp+=path[i];
            }
        }
        //根据names生成新的路径
        string ans="/";
        for(int i=0;i<cnt;i++){
            ans+=names[i];
            if(i!=cnt-1){
                ans+="/";
            }
        }
        return ans;
    }
};

2.3 编辑距离

只能说不愧是级别为困难是吧，好难顶，一开始的思路是最大公共子序列，但是没想起来怎么记录相等的序列以便回溯，好像之前遇到过，属实不应该😣

耗了一下午看了官方题解

被WA的思路：

class Solution {
public:
    int minDistance(string word1, string word2) {
        //找到最长公共子集，然后算删除和插入的个数
        int len1=word1.length();
        int len2=word2.length();
        vector<vector<int> >dp(len1);
        for(int i=0;i<len1;i++){
            dp[i].resize(len2);
            fill(dp[i].begin(),dp[i].end(),0);
        }
        vector<int>vis(len1);
        fill(vis.begin(),vis.end(),-1);
        //操作
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(word1[i]==word2[j]){
                    if(i&&j){
                        dp[i][j]=dp[i-1][j-1]+1;
                    }else{
                        dp[i][j]=1;
                    }
                }else{
                    if(i&&j){
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    }else if(i){
                        dp[i][j]=dp[i-1][j];
                    }else if(j){
                        dp[i][j]=dp[i][j-1];
                    }
                }
            }
        }
        int ans=dp[len1-1][len2-1];
        //公共子序列是ans个，还需要再补上len2-ans,需要改造的len1-ans
        //这个最好是实现逆推
        return max(len1,len2)-ans;
    }
};

参考【官方题解】

可以理解为，求两个串的编辑距离而不是一个串word1如何单向变为串word2,它们操作总结为三种：

word1插入一个字符

word2插入一个字符（等价于word1删除一个字符）

word1修改一个字符

所以用dp[i][j]来表示word1长度为i之前到word2长度为j之前的最短编辑距离，状态转移方程为：

dp[i][j]=Min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)(word[i]!=word[j])

dp[i][j]=Min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1])(word[i]==word[j])

class Solution {
public:
    int minDistance(string word1, string word2) {
        //找到最长公共子集，然后算删除和插入的个数
        int len1=word1.length();
        int len2=word2.length();
        if(len1*len2==0){
            return len1+len2;//如果之前是空串
        }
        vector<vector<int> >dp(len1+1,vector<int>(len2+1));//DP数组定义
        //初始化
        for(int i=0;i<=len1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=len2;j++){
            dp[0][j]=j;
        }
        //迭代
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                int a=dp[i][j-1]+1;
                int b=dp[i-1][j]+1;
                int c;
                if(word1[i-1]==word2[j-1]){
                    c=dp[i-1][j-1];
                }else{
                    c=dp[i-1][j-1]+1;
                }
                dp[i][j]=min(a,min(b,c));
            }
        }
        return dp[len1][len2];
    }
};