动态规划第五讲——leetcode上的标题动态规划汇总（上）

动态规划第五讲——leetcode上的题目动态规划汇总（上）
本节，我们将对leetcode上有关DP问题的题目做一个汇总和分析。

1.题目来源

Interleaving String 动态规划二叉树
Unique Binary Search Trees 动态规划二叉树
Word Break 动态规划 N/A
Word Break II 动态规划 N/A
Palindrome Partitioning 动态规划 N/A
Palindrome Partitioning II 动态规划 N/A
Triangle 动态规划 N/A
Distinct Subsequences 动态规划 N/A
Decode Ways 动态规划 N/A
Scramble String 动态规划 N/A
Maximal Rectangle 动态规划 N/A
Edit Distance 动态规划 N/A
Climbing Stairs 动态规划 N/A
Minimum Path Sum 动态规划 N/A
Unique Paths 动态规划 N/A
Unique Paths II 动态规划 N/A
Jump Game 动态规划 N/A
Jump Game II 动态规划 N/A
Maximum Subarray 动态规划 N/A
Wildcard Matching 动态规划 N/A
Substring with Concatenation of All Words 动态规划 N/A

2.题目分析

Eg1:word break

我们定义bool dp[i+1]为s(0~i)是否可以被分解，这样就能很容易得到递推式并求解

Eg2:wor break2：

相对上一题目而言，这道题目的结果变成了一个全路径的搜索问题；不仅要判断s是否可以分解，还要给出所有分解的方案.这算是DP问题的一种很典型的形式。如果我们用vector<vector<string> > dp[i+1]来存储解决方案，这样会导致空间的溢出O(n^3).所以，改进一下，这里我们并不存储全路径，而是存储部分路径。vector<int> dp[i+1], 能够匹配到dp[i+1]的上一个下标,这样空间复杂度是O(n^2).

分析2：第一步中，我们得到了一个有向无环图，现在的任务就是遍历这个图，求出所有的路径。这类似于一个普通树的深度优先搜索。代码如下

class Solution {                                                                                                                                     
public:         
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        VS result;                                           
		int n=s.size();
		if(n==0){
			result.push_back("");
			return result;
		}


		VI test;//dp[i]from 0 to n: the last part of path
		VVI dp( n+1, test);
		int i, t;
		for (i = 0; i < n; ++i){
			for (t = 0; t <i+1; ++t){
				if(t==0 || dp[t].size()!=0){//s[t-1] is ok!
					if(dict.find(s.substr(t, i+1 - t)) != dict.end()){
						dp[i+1].push_back(t);//forcus
					}
				}
			}
		}
		string path;
		if(dp[n].size()!=0)
		    result = bfs(n, dp, path, s);	
		return result;
	}


	VS bfs(int index, VVI const &dp, string path, string const &s){
		VS result;
		if(dp[index].size()==0){
			result.push_back(path.substr(1, path.length()));
			return  result;
		}
		int n= dp[index].size();
		int i;
		for (i = 0; i < n; ++i){
			VS pre;
			pre = bfs(dp[index][i], dp, " "+ s.substr(dp[index][i], index - dp[index][i])+path, s ) ;
			int size_pre = pre.size();


			int j;
			for(j=0; j<size_pre; j++){
				result.push_back(pre[j]);
			}
		}
		return result;	
	}
};

Eg 3:Palindrome Partitioning 动态规划 N/A

分析，这道题目和上一道有点类似，也是一个基于动态规划的全路径搜索问题。首先使用DP计算s[i,j]是否是回文；最后当然要加上一个步骤：采用dfs搜索全路径.
代码如下：

class Solution {
public:  
    vector<vector<string>> partition(string s) {
        int n = s.length();
        vector<vector<string> > res;
        vector<string> each;
        if(n < 2) {
            each.push_back(s);
            res.push_back(each);
            return res;
        }
       
        /* get state[i][j] */
        vector<bool> done(n, false);
        vector<vector<bool> > state(n, done);
        get_palindron_state(s, state);
        vector<string> pathed;
        dfs(s, state, n-1, pathed, res);
        return res;
    }    
       
    void get_palindron_state(string s, vector<vector<bool> > &state){
        int n = state.size();
        for (int i = n-1; i >=0 ; --i){
            for (int j = i; j < n; ++j){
                if(i==j) state[i][j]=true;
                else{
                    if(s[i] == s[j]){
                        if(i+1==j) state[i][j]=true;
                        else state[i][j]= state[i+1][j-1];
                    }
                }
            }
        }
    }   
       
    void dfs(const string &s,const vector<vector<bool> > &state,  int end, vector<string>  pathed, VVS &res ){
        for (int i = end; i >= 0; --i){     
            if(state[i][end]){   
                pathed.insert(pathed.begin(), s.substr(i, end-i+1));
                dfs(s,state,  i-1, pathed, res);
                pathed.erase(pathed.begin());
            }         
        }             
        if(end == -1){           
            res.push_back(pathed);
        }
    } 
    
};

Eg4:Palindrome Partitioning II

我们先求出state[i][j]:s(i, j)是否是回文；定义dp[i+1]表示s(i, s.length()-1)的最小分割数，最后dp[0]-1就是我们需要的结果。

dp[i] = min{dp[j+1] + 1| s(i, j)是回文}

Eg5:Triangle

太典型了，不讲。

Eg6:,Distinct Subsequences

分析：这道题目，可能初看之下，不能很好的想到使用动态规划求解—— 这是一个双序列类型的题目，熟练了以后就比较好往DP思考了。现在来看一下分析过程。

要求:numDistinct(string S, string T), if(S[0]!=T[0]) res = numDistinct(S(1, @), T);if(S[0]==T[0]) res= numDistinct(S(1, @), T(1, @))+numDistinct(S(1, @), T);通过分治法，我们已经发现了题目的显著特征：重叠子问题和最优子结构。接下来就是构造DP的问题了。
dp[i][j]:s(0,i), T(0,j)的numDistinct的数目，于是dp[i][j]= dp[i-1][j] + dp[i-1][j-1](if(S[i]==S[j]))

还是那句话：DP问题的难点不在于构造而在于识别。如果不能一眼看出DP问题的特征，那么就老老实实按照：问题是否可分；分解后子问题是否重叠；重叠的子问题是否满足最优子结构来判定。

class Solution {               
public:                        
    int numDistinct(string S, string T) {
        int i, j;              
        int m= S.length(), n=T.length();
        int dp[m][n];          
        if(m==0 || n==0 ) return 0;
        fill(dp[0], dp[0]+n, 0); 
        if(S[0]==T[0]) dp[0][0]=1;
        for (i = 1; i < m; ++i){
            dp[i][0]=dp[i-1][0];
            if(S[i]==T[0]) dp[i][0]++;
        }                      
                               
        for (i = 1; i < m; ++i){
            for(j=1; j<n; j++){
                dp[i][j] = dp[i-1][j];
                if(S[i]== T[j]) dp[i][j] += dp[i-1][j-1];
            }                  
        }                      
        return dp[m-1][n-1];                                                                                                                         
    }                          
};

Eg7:Decode Ways
分析：比较简单，如果不熟练可以先写出递归形似

class Solution {
public:             
       int numDecodings(string s) {
        int n=s.length();
        if(n==0 ) return 0;
        int i;  
        int dp[n+1];
        fill(dp, dp+n+1, 0);
        dp[0]=1;                                                                                                                                     
        if(isdigit(s[0] ) && s[0]!='0') dp[1]= 1;
        else dp[1]=0;
        if(n==1) return dp[1];
        for (i = 1; i < n; ++i){
            if(isdigit(s[i]) && s[i]!='0') dp[i+1] += dp[i];
            if(s.substr(i-1, 2) >= string("10") && s.substr(i-1, 2) <= string("26")) dp[i+1] += dp[i-1];
        }       
        return dp[n];
    }               
};

Eg8:Scramble String

分析，很显然，这又是一个双序列问题。但是，这道题目却并不是那么容易分析，因为组成一个问题的子问题多而复杂—— 这也是DP的难点所在。
isScramble(string s1, string s2){
int n=s1.length();
for (int i = 1; i < n; ++i){//len
res ||= isScramble(s1.first, s2.first) && isScramble(s1.second, s2.second)
|| isScramble(s1.first, s2.second) && isScramble(s1.second, s2.first);
//为了方便，我们用firt代表s1的前半部分，
if(res = true) return true;
}
return false；
}

这是这个问题的递归解法，也是最直观的解法；首先，子问题可分是肯定的;另外，通过对子问题的观察，我们发现的确有子问题重叠现象，现在就剩下如何定义DP了。

直观的反应是这样定义：dp[i1][i2][j1][j2]:s(i1,i2), s2(j1, j2)是isScramble？但是这里有一个隐含的条件，如果是true的话，i2-i1 == j2-j1；于是，我们重新定义dp[i][j][l]:s1从i开始，s2从j开始，长度为l的字串是否满足Scramble。具体实现的代码如下：

class Solution {                                                                                                                                     
public:                                
    bool isScramble(string s1, string s2) {                                                                
        int n1=s1.length();            
        int n2=s2.length();            
        if(n1!=n2)                     
            return false;              
        bool dp[n1][n1][n1+1];
        memset(dp, false, sizeof(dp));
        /* dp[i][j][k]  start of s1, j:start of s2, k len of them */        
        int i, j, k, l;
        for (i = 0; i < n1; ++i){
            for (j = 0; j < n1; ++j){
                dp[i][j][1] = (s1[i]==s2[j]);
            }  
        }   
        for(k=2; k<=n1;k++){
            for(i=0; i+k<=n1; i++){
                for (j = 0; j+k <= n1; ++j){
                    for(l=1; l<k; l++){
                        if( (dp[i][j][l] && dp[i+l][j+l][k-l]) || (dp[i][j+k-l][l] && dp[i+l][j][k-l])){
                            dp[i][j][k] = true;
                            break;
                        }   
                    }   
                }   
            }  
        }   
        return dp[0][0][n1];
    }                                  
};

Eg9:Maximal Rectangle

这道题，DP是其中一个比较小的环节，用户数据预处理，dp[i][j]第i行j列上的元素往上延伸的1的个数。剩下的，就是另外一道题目的变形：最大直方图。

class Solution {   
public:      
    int maximalRectangle(vector<vector<char> > &matrix) {      
        int row_len = matrix.size();
        if(row_len == 0) return 0;
        int col_len = matrix[0].size();
        if(col_len ==0 ) return 0;
        vector<int> height(col_len, 0);
        vector<int> lastheight(col_len, 0);
        int res=0;
         
        for (int i = 0; i < row_len; ++i){
            for( int j=0; j<col_len ; j++){
                if(matrix[i][j] == '1'){
                    height[j]=lastheight[j]+1;
                }
                else
                    height[j]=0;
            }      
            res = max(res, largest(height));
            lastheight = height;
        }
        return res;
    } 
    
    int largest(vector<int> height) {   
        height.push_back(0);// be cautious
        stack<int> stk;  
        int i = 0;  
        int maxArea = 0;  
        while(i < height.size()){  
            if(stk.empty() || height[stk.top()] <= height[i]){  
                stk.push(i++);  
            }else {   
                int t = stk.top();  
                stk.pop();  
                maxArea = max(maxArea, height[t] * (stk.empty() ? i : i - stk.top() -1));  
            }
        }
        return maxArea;  
    }   
};

Eg9:Edit Distance

这也是一个典型的双序列问题，分析方法同上，代码如下

class Solution {

public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        int dp[len1+1][len2+1];
        for (int i = 0; i < len1+1; ++i){
            dp[i][0]=i;
        }   
        for (int i = 0; i < len2+1; ++i){
            dp[0][i]=i;
        }   
        int i, j;
        for (i = 0; i < len1; ++i){
            for (j = 0; j < len2; ++j){
                if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j];
                else {
                    dp[i+1][j+1] = min(dp[i][j], min(dp[i+1][j], dp[i][j+1])) +1 ;
                }   
            }   
        }   
        return dp[len1][len2];
    }   
};

(未完待续)

动态规划第五讲——leetcode上的标题动态规划汇总（上）

1.题目来源

2.题目分析

相关推荐