ACM動態(tài)規(guī)劃

dinghj 2019-09-22

展開全文

最近在lintcode上面刷dp算法，因為本菜鳥的dp實在是很渣，所以下定決心從簡單的題目刷起。

我會挑選幾個我覺得做起來不是那么得心應(yīng)手的題目，把ac以及效率高的代碼放上來。

中等題：

667.最長的回文序列

int longestPalindromeSubseq(string &s) {
        // write your code here
        int len = s.length(),dp[len+1][len+1];
        memset(dp,0,sizeof(dp));
        for(int i = len-1;i>=0;i--){
            dp[i][i] = 1;
            for(int j = i+1;j<len;j++)
                if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1]+2;
                else dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
        }
        return dp[0][len-1];
    }

分析：線性dp的共性，找串與串之間的聯(lián)系

---假設(shè)s[i] != s[j]

那么在sub(i,j)的最大回文串中,s[i]與s[j]不會同時出現(xiàn)，那么sub(i,j)的最大回文串要么出現(xiàn)在sub(i+1,j),要么出現(xiàn)在sub(i,j-1)，因此我們的狀態(tài)轉(zhuǎn)移方程就得到了

---假設(shè)s[i]==s[j]

那么直接認為這倆個匹配，會同時出現(xiàn)在結(jié)果中，然后加上sub(i+1,j-1)的最大回文串即可

簡單的dp方程，但是要注意的是i和j的遍歷方向，因為對于串sub(i,j),如果需要用到sub(i+1,j-1)的值，那么dp(i+1,j-1)應(yīng)該在之前已經(jīng)求出來，所以我們需要順著i減小的方向遍歷，j增大的方向遍歷

延伸到其他問題：

1. 給定一串字符，判斷這個字符的非空子串（連續(xù)的）有多少個是回文串。

暴力解（非dp，但是不包括像線段樹那樣的數(shù)據(jù)結(jié)構(gòu)的其他解法）：先N^2暴力每個區(qū)間，然后n判斷回文，總的復(fù)雜度n^3

優(yōu)化解（dp，減少重復(fù)子問題的重復(fù)遍歷）：dp一次，O（n^2）的復(fù)雜度，然后再n^2遍歷所有區(qū)間，判斷即可。

2.給定一串字符，判斷這個字符串的最大回文子串的長度（注意和母題區(qū)分，母題是求子序列即非連續(xù)）。（此處是連續(xù)的）

算法：馬拉車算法。時間復(fù)雜度O（n）

119.編輯距離

 int minDistance(string &word1, string &word2) {
        // write your code here
        int lenx = word1.length(),leny = word2.length(),dp[lenx+1][leny+1];
        for(int i = 0;i<=lenx;i++) dp[i][0] = i;
        for(int i = 0;i<=leny;i++) dp[0][i] = i;
        for(int i = 1;i <= lenx;i++){
            for(int j = 1;j <= leny;j++){
                if(word1[i-1]==word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min( dp[i-1][j] ,min( dp[i][j-1], dp[i-1][j-1] ) )+1;
            }
        }
        return dp[lenx][leny];
    }

分析：

1.類比一下最長公共子序列，發(fā)現(xiàn)應(yīng)該是二維的狀態(tài)方程類型。

2.接著就是找狀態(tài)轉(zhuǎn)移方程。

dp的初始狀態(tài)就不詳細說明了，現(xiàn)在準備求dp(i,j),

---假設(shè)word1[i] == word2[j]

那么我們就認為這倆個字符是匹配的，所以可能的一種結(jié)果就會是dp[i-1][j-1] ，狀態(tài)轉(zhuǎn)移方程dp(i,j) = dp(i-1,j-1)

---假設(shè)word1[i] != word2[j]

那么我們可以認為因為這倆個字符不相同，導(dǎo)致一定會在前一個狀態(tài)下新增加一個操作，那么前一個狀態(tài)是什么呢？

不難發(fā)現(xiàn)，前一個狀態(tài)肯定是有三個的，假如對這倆個字符的有無的狀態(tài)進行編碼，有四種狀態(tài)，而當(dāng)前的dp(i,j)是一種，

另外的三種情況就是dp(i-1,j-1),dp(i-1,j),dp(i,j-1)，結(jié)果一定是從這三種中得到的，因為我們的if的條件判斷只涉及到ij倆個字符的討論，這也是線性dp的一個特點。所以另外一個狀態(tài)轉(zhuǎn)移方程就是

dp(i,j) = min(dp(i-1,j-1),dp(i-1,j),dp(i,j-1)) +1

77.最長公共子序列

int longestCommonSubsequence(string &A, string &B) {
        // write your code here
        int lenx = A.length(),leny = B.length();
        int dp[lenx+1][leny+1];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i<=lenx;i++)
            for(int j = 1;j<=leny;j++)
                if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] +1;
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]) ;
        return dp[lenx][leny];
    }

最簡單的模型

108 分割回文串

題目大意：將輸入的字符串進行k次分割，使得分割后的所有串全是回文串，求最小的分割次數(shù)k

TLE代碼：暴力求解

int minCut(string &s) {
        // write your code here
        int len = s.length(),dp1[len+1][len+1],dp[len+1][len+1];
        memset(dp1,0,sizeof(dp1));
        memset(dp,0,sizeof(dp));
        for(int i = 1;i<=len;i++){
            dp1[i][i] = 1;
            dp[i][i] = 0;
        }
        for(int i = len-1;i>=0;i--){
            for(int j = i+1;j<len;j++){
                if(s[i] == s[j]) dp1[i][j] = dp1[i+1][j-1] + 2;
                else dp1[i][j] = max(dp1[i+1][j],dp1[i][j-1]);
                if(j-i+1 == dp1[i][j]) dp[i][j] = 0;
                else{
                    int Min = 1e9;
                    for(int k = i;k<j;k++){
                        Min = min(Min,dp[i][k] + dp[k+1][j]+1);
                    }
                    dp[i][j] = Min;
                }
            }
        }
        return dp[0][len-1];
    }

稍作優(yōu)化：將預(yù)處理后的結(jié)果（可以判斷出任意子串是否是回文串) 再一維dp即可

int minCut(string &s) {
        // write your code here
        int len = s.length(),dp1[len+1][len+1],dp[len+1];
        memset(dp1,0,sizeof(dp1));
        memset(dp,0,sizeof(dp));
        for(int i = 0;i<=len;i++) dp1[i][i] = 1;
        for(int i = len-1;i>=0;i--){
            for(int j = i+1;j<len;j++){
                if(s[i] == s[j]) dp1[i][j] = dp1[i+1][j-1] + 2;
                else dp1[i][j] = max(dp1[i+1][j],dp1[i][j-1]);
            }
        }
        for(int i = len-1;i>=0;i--){
            int Min = 1e9;
            if(dp1[i][len-1] == len-i){
    			dp[i] = 0;
    			continue;
    		}
            for(int k = i;k<len-1;k++)
                if(dp1[i][k] == k-i+1) Min = min(Min,dp[k+1] + 1);
            dp[i] = Min==1e9?0:Min;
        }
        return dp[0];
    }

因為區(qū)間可以完全判斷是否是回文串，所以一定是優(yōu)先考慮包含回文串的區(qū)間的最值

這次結(jié)果居然時間超過其他人了。。

感覺練了上面那些問題后，進步不少了，看到題目能分辨出是區(qū)間dp還是線性dp，下面的題目也容易的分析出最優(yōu)解的結(jié)構(gòu)

上菜：

670.預(yù)測能否勝利

簡單的區(qū)間dp，dp存下區(qū)間選擇的最優(yōu)解，然后每次需要往前推倆步才能到達下一個狀態(tài)，因為是倆個人輪流選數(shù)，并且要考慮對手也是選擇最優(yōu)解（就是那個最小值的操作，對手一定是把較小的選擇方案留給自己了）。

bool PredictTheWinner(vector<int> &nums) {
        // write your code here
        int n = nums.size(),sum = 0;
        int dp[n][n];
        memset(dp,0,sizeof(dp));
        for(int i = 0;i<n;i++) dp[i][i] = nums[i],sum+=nums[i];
        for(int i = n-1;i>=0;i--) 
            for(int j = i+1;j<n;j++){
                int len = j-i+1;
                if(len == 2) dp[i][j] = max(nums[i],nums[j]);
                else dp[i][j] = max(nums[i] + min(dp[i+2][j],dp[i+1][j-1]),nums[j] + min(dp[i][j-2],dp[i+1][j-1]));
            }
        return (dp[0][n-1]<<1)>=sum;
    }

603.最大整除子集

根據(jù)需要的解分析，倆倆數(shù)之間必須成倍數(shù)關(guān)系，那么排序之后，每個數(shù)都必須是前面所有數(shù)的倍數(shù)。

所以先對數(shù)組排序，然后dp[i]表示第i個數(shù)放在集合里面能找到的最大集合的元素個數(shù)。

那么對每個i ，遍歷[0，i-1] 使得 nums[i]%nums[j] == 0 即有點像最長上升子序列的dp方程。

然后我們最后找到最大的dp[i]就完事了。但是答案需要把每個元素輸出，所以每次求dp[i]的時候記錄下能被nums[i]整除的最大dp[j]的位置就好了，然后通過pre來找到這個最大的路徑。有點像最短路算法用pre記錄路徑的方法。

vector<int> largestDivisibleSubset(vector<int> &nums) {
        // write your code here
        int n = nums.size(),lens=0,pos=0;
    	int dp[n],pre[n];
    	sort(nums.begin(),nums.end());
    	memset(dp,1,sizeof(dp));
    	memset(pre,-1,sizeof(pre));
    	for(int i = 1; i<n; i++) {
    		int p,Max = 0;
    		for(int j = 0; j<i; j++) {
    			if(nums[i]%nums[j] == 0) {
    				Max = i==j?0:dp[j];
    				p = j;
    			}
    		}
    		if(Max){
    		    dp[i] = Max + 1;
    		    pre[i] = p;
    		}
    		if(dp[i]>lens) {
    			lens = dp[i];
    			pos = i;
    		}
    	}
    	vector<int> ans;ans.clear();
    	while(pos!=-1) {
    		ans.push_back(nums[pos]);
    		pos = pre[pos];
    	}
       return ans;
    }

但是 >---< ，時間復(fù)雜度讓我不滿意。

dp優(yōu)化方案：

191.乘積最大序列

思路還是挺簡單的，線性dp，但是要注意的是，需要維護每個階段的最大值和最小值，因為當(dāng)前數(shù)值可能是負數(shù)，那么最大值會從（上一個階段的負數(shù)乘積當(dāng)前負數(shù)）產(chǎn)生，所以倆個dp 一個維護最大值，一個維護最小值即可。

int maxProduct(vector<int> &nums) {
        // write your code here
        int n = nums.size(),ans = -2e9;
        int dp1[n],dp2[n];
        for(int i = 0;i<n;i++) dp1[i] = dp2[i] = nums[i];
        ans = nums[0];
        for(int i = 1;i<n;i++){
            int a = dp1[i-1]*nums[i],b = dp2[i-1]*nums[i];
            dp1[i] = min(a,min(b,nums[i]));
            dp2[i] = max(a,max(b,nums[i]));
            ans = max(ans,dp2[i]);
        }
        return ans;
    }

436.最大正方形

線性dp dp[i][j]表示以matrix[i][j]為頂點的最大正方形的邊長，那么限制它的就是相鄰的三個位置，

開心，時間效率最高的 n^2復(fù)雜度

int maxSquare(vector<vector<int>> &matrix) {
        // write your code here
        int ans = 0,n = matrix.size(),m = matrix[0].size();
        int dp[n][m];
        for(int i = 0;i<n;i++) dp[i][0] = matrix[i][0],ans = max(ans,dp[i][0]);
        for(int i = 0;i<m;i++) dp[0][i] = matrix[0][i],ans = max(ans,dp[0][i]);
        for(int i = 1;i<n;i++)
            for(int j = 1;j<m;j++)
                if(matrix[i][j]) dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1,ans = max(ans,dp[i][j]);
                else dp[i][j] = 0;
        return ans*ans;
    }

但是還有其他的方案：

例如：前綴和。先預(yù)處理求出前綴和，然后對于每個點，遍歷其他的所有對角頂點，使得這個正方形區(qū)域的求和是等于覆蓋的面積的。然而這個時間復(fù)雜度是n^3多了遍歷的操作，代碼就不上了。

116.跳躍游戲

1. 貪心每次更新能達到的最遠端，如果當(dāng)前遍歷的位置i大于最遠端則退出（即不能跳躍），最后判斷最右端是否到達數(shù)組最后

int max(int a,int b){
        return a>b?a:b;
    }
    bool canJump(vector<int> &A) {
        // write your code here
        int Max = 0,len = A.size();
        for(int i = 0;i<len;i++){
            if(i>Max) break;
            Max = max(Max,i + A[i]);
        }
        return Max>=len-1;
    }

2. dp[i] 判斷位置i是否可達，每次從[0,i-1]尋找可以到達i的點，如果不存在就無法跳躍到dp[i]

bool canJump(vector<int> &A) {
        // write your code here
        int Max = 0,len = A.size();
        bool dp[len];
        for(int i = 0;i<len;i++) dp[i] = false;
        dp[0] = true;
        for(int i = 1;i<len;i++){
            for(int j = i-1;j>=0;j--)
                if(dp[j] == true && j + A[j] >= i){
                    dp[i] = true;break;
                }
        }
        return dp[len-1];
    }

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊一鍵舉報。