C++算法集锦：动态规划（二）

• 单词拆分(一)
• 单词拆分(二)
• 最长公共子数组
• 压缩字符串(一)

牛客链接:NC181 单词拆分(一)

题解1：DFS

每次从字符串中从头开始选择定长的子字符串去集合中寻找对应目标，如果存在，则继续这么操作寻找后续字符串。如果找到最后，字符串为0了，那么说明字符串集合能够组成这个字符串。

class Solution {
public:
    
    bool wordDiv(string s, vector& dic) {
        // write code here
        if(s.size() == 0)
            return true;
        int ans = false;
        for(int i =0;i<=s.size();++i){   //递归查找
            string temp = s.substr(0,i);
            if(find(dic.begin(), dic.end(), temp) != dic.end())
            {
                ans = wordDiv(s.substr(i), dic);
            }
            if(ans == true)   //截枝
                break;
        }
        return ans;
    }
};

题解2：动态规划

设定一个dp数组，初始化为0。其中dp[i]=1表示以i结尾的字符串能够通过集合组合而成。 当前dp[i]可以通过前j个字符串和j-i字符串组合而成，如果dp[j]=1，且i-j的子字符串在集合中，则dp[i] =1;

class Solution {
public:
    
    bool wordDiv(string s, vector& dic) {
        // write code here
        unordered_set us;  //保所有出现过的字符串
        for(string sub:dic)
            us.insert(sub);
        
        bitset<501> dp = 0;   //比vector更快
        dp[0] = 1;								
        for(int i =1;i<=s.size();++i){     //遍历之后的每一位
            for(int j =0;j          //截取字符串长度
                if(dp[j] && us.find(s.substr(j,i-j)) != us.end()) //能表示直接退出循环。
                {
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

牛客链接:NC182 单词拆分(二)

解法1：DFS

深度搜索每个可能的同时，加其加入到子答案中。当s剩余0时，子答案加入答案集合，否则不成立，他不是一个子答案。

class Solution {
public:
    
    void dfs(string s, string sub_ans, vector& dic, vector &ans){  //dfs
        if(s.size() == 0){
            sub_ans.erase(0, 1); //去掉开头的空格
            ans.push_back(sub_ans);
            return;
        }
        for(int i = 0;i<=s.size();++i)  
        {
            if(find(dic.begin(),dic.end(),s.substr(0,i))!=dic.end())
            {
                string temp = sub_ans;
                sub_ans = sub_ans +" "+s.substr(0,i);
                dfs(s.substr(i), sub_ans, dic, ans);
                sub_ans = temp;
            }
        }
    }
    
    vector wordDiv(string s, vector& dic) {
        // write code here
        vector ans;
        dfs(s,"",dic,ans);
        return ans;
    }
};

牛客链接：NC183 最长公共子数组

解法1：动态规划

定义一个二维数组ans[i][j]，其中ans[i][j]表示以A中第i个元素和B中第j个元素结尾的最长后缀序列的长度，递推关系如下：
如果A[i-1] == B[j-1]，则ans[i][j] = ans[i-1][j-1] + 1; 即在原有的基础后缀基础上加上延伸一个。
否则，后缀不存在，重新计算后缀，ans[i][j] = 0；

class Solution {
public:
    
    int longestCommonSubarry(vector& A, vector& B) {
        // write code here
        if(A.size() == 0 or B.size() == 0)
            return 0;
        int res = 0;
        vector> ans(A.size()+1,vector(B.size()+1,0));
        for(int i =1;i<=A.size();++i){         
            for(int j =1;j<=B.size();++j){   
                if(A[i-1] == B[j-1])  
                    ans[i][j] = ans[i-1][j-1] + 1;         //可以优化
                else{
                    ans[i][j] = 0;
                }
                res = max(res, ans[i][j]);
            }
        }
        return res;
    }
};

这里可以通过使用一维数组滑动更新，实现空间优化。每次都要利用第j-1个信息，因此要先更新j在更新j-1。
每次更新的时候通过扫描前一个字符与当前字符是否相等，来考虑当前是否能够通过前一个最长序列来延续，以此省掉第一个维度。

class Solution {
public:
    
    int longestCommonSubarry(vector& A, vector& B) {
        // write code here
        if(A.size() == 0 or B.size() == 0)
            return 0;
        int res = 0;
        vector ans(B.size()+1,0);
        for(int i = 1; i<=A.size(); ++i){
            for(int j = B.size(); j>=0; --j){
                if(A[i-1] == B[j-1])
                    ans[j] = ans[j-1] + 1;
                else{
                    ans[j] = 0;
                }
                res = max(res, ans[j]);
            }
        }
        return res;
    }
};

牛客链接：NC101 压缩字符串(一)

解法1：栈

从头到尾遍历，出现不同的元素，统计栈内元素个数，为1则不需要输出，同时清空栈，用于计算下一个元素。

class Solution {
public:
    
    string compressString(string param) {
        // write code here
        stack s;
        string ans = "";
        if(param.size() == 0)
            return ans;
        for(int i =0; i
            if(s.size()==0 or param[i] == s.top())
                s.push(param[i]);
            else{
                ans+=s.top();
                if(s.size()>1)
                    ans+=to_string(s.size());
                while(s.size()>0)
                    s.pop();
                s.push(param[i]);
            }
        }
        ans+=s.top();
        if(s.size()>1)
            ans+=to_string(s.size());
        return ans;
    }
};