数塔问题和最长上升子序列问题
1.數(shù)字三角形問題
?
題意：給定一個數(shù)字三角形，從最上面出發(fā)往下走，每次只能走左下或者右下，求所有路徑中最大的和。
?
分析：形狀就跟楊輝三角形一樣，那么，設(shè)原數(shù)組為a[][],設(shè)從底邊到第i行第j列所走的路徑中最大和為dp[i][j]。
那么，很明顯有dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + a[i][j];
?
?
2.最長上升子序列問題
?
分析：對于一個數(shù)列a[]來說，我們用dp[i]來表示以a[i]結(jié)尾的序列的最長上升子序列，那么假設(shè)現(xiàn)在我們知道了i之前的所
有dp[j]，其中0<=j<i，那么狀態(tài)轉(zhuǎn)移方程為：dp[i] = max(dp[i],dp[j] + 1) ,0<=j<i,a[j]<a[i]。本算法的時間
復(fù)雜度為O(n^2)。
?
int Work(int a[],int n) {int ans = -1;for(int i=0;i<n;i++)dp[i] = 1;for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(a[i] > a[j])dp[i] = max(dp[i],dp[j] + 1);}ans = max(ans,dp[i]);}return ans; }
其實(shí)還有O(nlog(n))的算法。現(xiàn)在來介紹一下：
根據(jù)dp[]的值進(jìn)行分類。對于dp[]的每一個取值k，我們只需要保留滿足dp[t] = k的所有a[t]中的最小值。設(shè)d[k]記錄這個值，即d[k] = min{a[t]}? (dp[t] = k)。
注意到d[]的兩個特點(diǎn)： ? (1) d[k]的值是在整個計算過程中是單調(diào)不上升的。 (2) d[]的值是有序的，即d[1] < d[2] < d[3] < ... < d[n]。 ? ? 利用d[]，我們可以得到另外一種計算最長上升子序列長度的方法。 設(shè)當(dāng)前已經(jīng)求出的最長上升子序列長度為len。先判斷a[t]與d[len]。 若a[t] > d[len]，則將a[t]接在a[len]后將得到一個更長的上升子序列，len = len + 1， d[len] = a[t]； 否則，在d[1]..d[len]中，找到最大的j，滿足d[j] < a[t]。令k = j + 1，則有d[j] < a[t] <= d[k]，將a[t]接在 d[j]后將得到一個更長的上升子序列，同時更新d[k] = a[t]。最后，len即為所要求的最長上升子序列的長度。?
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h>using namespace std; const int N = 100005; const int INF = ~0U>>1;int a[N],d[N];int Binary_Search(int l,int r,int x) {while(l < r){int m = (l + r) >> 1;/** 非嚴(yán)格上升子序列，如果是嚴(yán)格上升子序列，應(yīng)該把下面的<=改為<即可 */if(x <= d[m]) r = m;else l = m + 1;}return l; }int Work(int a[],int n) {d[0] = -1;int max = -1;int len = 1;for(int i=1;i<=n;i++){d[len] = INF;int j = Binary_Search(0,len,a[i]);if(j == len) len++;d[j] = a[i];}return len - 1; }int main() {int n;while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);printf("%d\n",Work(a,n));}return 0; }
?
?
題目：http://acm.hdu.edu.cn/showproblem.php?pid=1087
?
題意：給定一個序列a[]，求這個序列的子序列中和最大的值。
?
分析：這個題比較有意思，跟最長上升子序列相比，不同點(diǎn)是最長上升子序列求的是上升長度最大值，而本題是求上升的和最
大值，那么可以類比。我們知道在最長上升子序列中的狀態(tài)轉(zhuǎn)移方程是：dp[i] = max(dp[i],f[j] + 1),0<=j<i,a[j]<a[i]。
那么對于和同樣的思路得到：dp[i] = max(dp[i],dp[j] + a[i]),0<=j<i,a[j]<a[i]。
int Work(int a[],int n) {int ans = -1;for(int i=0;i<n;i++)dp[i] = a[i];for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(a[i] > a[j])dp[i] = max(dp[i],dp[j] + a[i]);}ans = max(ans,dp[i]);}return ans; }
?
?
總結(jié)
以上是生活随笔為你收集整理的数塔问题和最长上升子序列问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
