lintcode 动态规划问题

前言

第二周我们计划刷动态规划的题目，由于题目较多。我们选取出现频率最高的十道题目。

此次参与刷题的有五人（嘟嘟、琼琼、东东、大智、博主）

正题

94.二叉树中的最大路径和

1.dp[father] = max(dp[left],dp[right],0) + a[father]

到父亲结点的最大值等于（左边或者右边或者都不取里面的最大值）。

2.当然全局最大值也可以是以父亲结点为中间结点把左边和右边连接起来，这样的最大值是max(dp[left]+dp[right],0) + a[father]。

代码：

class Solution {
public:
    /*
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int res;
    int dfs(TreeNode *cur){
        if(cur==NULL) return 0;
        int left = dfs(cur->left);
        int right = dfs(cur->right);
        if(max(left+right,0)+cur->val>res)
            res = max(left+right,0)+cur->val;
        return max(max(left,right),0)+cur->val;
    }
    
    int maxPathSum(TreeNode * root) {
        // write your code here
        res = -1e9;
        int ans = dfs(root);
        return max(ans,res);
    }
};

510.最大矩形（好题！）

题意是要求一堆0 1组成的矩阵中，最大全为1的矩形的面积。

要求最大面积，我们可以联想到上一篇博客中讲到的直方图中最大矩形的面积（leetcode 84、lintcode 122）

区别于之前的题目，我们需要构造高度矩阵。

我们可以遍历每一行。

第一行，如果是1，高度为1。如果是0，高度为0。（这个很容易理解）

第i行，如果是1，第i-1行的高度+1，如果是0，高度为0。

【如果是0，会清零；如果是1，会累加】

最大的面积一定在其中。

AC代码：

class Solution {
public:
    /*
     * @param matrix: a boolean 2D matrix
     * @return: an integer
     */
    int largestRectangleArea(vector<int> heights) {  
        int len = heights.size(),res=0;  
          
        stack<int> stac;  
        for(int i=0;i<=len;++i){  
            while(!stac.empty()&&heights[stac.top()]>heights[i]){  
                int tmp = heights[stac.top()];  
                stac.pop();  
                tmp = stac.empty()?tmp*i:tmp*(i-1-stac.top());  
                res = max(res,tmp);  
            }  
            stac.push(i);  
        }  
        return res;  
    }  
    
    int maximalRectangle(vector<vector<bool>> &matrix) {
        // write your code here
        int m = matrix.size();
        if(m==0) return 0;
        int n = matrix[0].size(),i,j,res=-1;
        vector<int> h(n+1,0);

        for(i=0;i<m;++i){
            for(j=0;j<n;++j)
                h[j]=matrix[i][j]?h[j]+1:0;
            res=max(res,largestRectangleArea(h));
        }
        return res;
    }
};

119.编辑距离

dp[i][j]=dp[i-1][j-1]; 【word1[i]==word2[j]】
dp[i][j]=min(dp[i][j-1] 插入word2[j], dp[i-1][j] 删除word1[i], dp[i-1][j-1] word1[i]替换为word2[j])+1;【word1[i]！=word2[j]】

512.解码方法

dp[i]=dp[i-2](s[i-1],s[i]组成的数字在10-26)+dp[i-1](s[i]组成的数字在1-9)

可以使用滚动数组节省空间。

163.不同的二叉查找树

对于n，枚举每一个数字i作为根结点，左边有i-1个结点，右边有n-i个结点。

而之前已经求得i-1和n-i个结点的二叉查找树的个数dp[i-1]和dp[n-i]。

因此dp[n]=枚举所有的i的乘积（dp[i-1]*dp[n-i]）和。

191.乘积最大子序列

上一篇博客已经讲到。

只用记录之前的最大和最小即可。（最小的乘以负的等于最大）

392.打劫房屋

相邻的房子只能打劫一个，求最大值。

dp[i] = max(dp[i-1],dp[i-2]+a[i])

滚动数组。

107.单词拆分1

给一个字符串s和一个字典，判断字符串s可否被字典中的单词切分（一个或多个）

做法1: 

dp[i]表示到第i个位置是否可拆分，那么我们需要判断dp[j]（j<i）和s[j:i]是否存在dict中即可。

算法复杂度：O（n^2）

到96%的数据会超时。

代码：

class Solution {
public:
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    bool wordBreak(string &s, unordered_set<string> &dict) {
        int len = s.length();
        vector<bool> dp(len+1,false);
        dp[0]=true;
        for(int i=1;i<=len;++i)
            for(int j=i-1;j>=0;--j)
                if(dp[j]&&dict.count(s.substr(j,i-j))>0){
                    dp[i]=true;
                    break;
                }
        return dp[len];
    }
};

做法2:

我们可以对做法1做一个优化，对i这个位置，我们往前看字典中的词是否存在即可。

算法复杂度：O（n*m）

AC代码： 400ms

class Solution {
public:
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    bool wordBreak(string &s, unordered_set<string> &dict) {
        // write your code here
        int len = s.length(),d_len = dict.size();
        unordered_set<string>::iterator it;
        vector<int> s_len(d_len);
        int i=0,j;
        for(it=dict.begin();it!=dict.end();it++)
            s_len[i++]=(*it).length();
       
        vector<bool> dp(len+1,false);
        dp[0]=true;
        for(i=1;i<=len;++i){
            j=0;
            for(it=dict.begin();it!=dict.end();it++){
                if(i>=s_len[j]&&dp[i-s_len[j]]&&s.substr(i-s_len[j],s_len[j])==*it){
                    dp[i]=true;
                    break;
                }
                j++;
            }
        }
        return dp[len];
    }
};

做法3: 前缀树（也叫Trie树、字典树）

参考：* Trie树、Trie树CSDN

我们的做法是初始化根结点（每个结点有26个孩子表示a-z），当然最开始孩子结点都为NULL。

把dict中的每一个词依次插入到Trie树中，结点的isEnd表示从根到当前结点是否构成一个词。

PS：需要把string转化为char *，传指针，不然会爆内存！

代码： 1636ms

class Solution {
public:
    /*
     * @param s: A string
     * @param dict: A dictionary of words dict
     * @return: A boolean
     */
    struct TrieTreeNode{
        bool isEnd;
        TrieTreeNode *child[26];

        TrieTreeNode(){
            memset(child,0,sizeof(child));
            isEnd=false;
        }
    };

    TrieTreeNode *root = new TrieTreeNode();
    bool res;

    void Insert(string word){
        TrieTreeNode *p = root;
        int len = word.length();
        for(int i=0;i<len;++i) {
            if (p->child[word[i]-'a'] == NULL)
                p->child[word[i]-'a'] = new TrieTreeNode();
            p = p->child[word[i]-'a'];
        }
        p->isEnd = true;
    }
    
    void find(const char *s){
        if(res) return;
        int len = strlen(s);
        if(len==0){
            res=true;
            return;
        }
        TrieTreeNode *p = root;
        for(int i=0;i<len;++i){
            p = p->child[s[i]-'a'];
            if(p == NULL) return;
            if(p->isEnd) find(s+i+1);
        }
        return;
    }
    
    bool wordBreak(string &s, unordered_set<string> &dict) {
        for(unordered_set<string>::iterator it=dict.begin();it!=dict.end();it++)
            Insert(*it);
        res=false;
        const char *str = s.c_str();
        find(str);
        return res;
    }
};

154.正则表达式匹配

根据模式串p的长度来进行分：

p长度为0，s长度为0（true），其他false。

p长度为1，s长度为1，并且两个字匹配。

p长度>1，且p[1]!='*'。看第一个字是否能匹配。

p长度>1，且p[1]=='*'。匹配0个字，匹配1个字。

PS：三角兽面试题

代码：

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
    bool dfs(string s,string p){
        if(!p.length()) return !s.length();
        if(p.length()==1) return (s.length()==1&&(s[0]==p[0]||p[0]=='.'));
       
        if(p[1]!='*') return s.length()&&(s[0]==p[0]||p[0]=='.')&&dfs(s.substr(1),p.substr(1));
        else{
            if(dfs(s,p.substr(2))) return true;
            if(s.length()>0&&(s[0]==p[0]||p[0]=='.')) return dfs(s.substr(1),p);
        }
        return false;
    }
    
    bool isMatch(string s, string p) {
        // write your code here
        return dfs(s,p);
    }
};

111.爬楼梯

dp[i]=dp[i-1]+dp[i-2]

滚动数组。