【前言】動态規劃:與分治法相似,即通過組合子問題來求解原問題,不同的是分治法是将問題劃分為互不相交的子問題,遞歸求解子問題,再将他們組合起來求出原問題的解。
動态規劃則應用于子問題重疊的情況,通常用來求解最優化問題。這類問題可以有很多可行解,每個解都有一個值,我們希望尋找最優值的解。
通常有4個步驟來設計動态規劃算法:
1.刻畫一個最優解的結構特征。
2.遞歸地定義最優解的值。
3.計算最優解的值,通過采用自底向上的方法。
4.利用計算出的資訊構造一個最優解。
【問題1】最長遞增子序列問題
【問題描述】設L=<a1,a2,…,an>是n個不同的實數的序列,L的遞增子序列是這樣一個子序列Lin=<ak1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
采用一個數組temp[]儲存 以目前元素結尾的最長遞增子序列長度,最後求出全局最優解
更新最長遞增子序列的條件:a[i]>a[j] (i>j) 且前一個遞增序列長度大于等于目前遞增序列長度
//動态規劃過程是:每次決策依賴于目前狀态,又随即引起狀态的轉移。
//最長遞增子序列O(N^2)
public void longestIncreasingSubsequence2(int[] a){
int[] temp=new int[a.length];
temp[0]=1;
int max=0;
for(int i=1;i<a.length;i++){
temp[i]=1;
for(int j=0;j<i;j++){
if(a[i]>a[j]&&temp[i]<=temp[j]){//找出最大的temp[j](前一個最長遞增子序列長度)temp[i]<=temp[j]
temp[i]=temp[j]+1;//更新最長遞增子序列長度
}
}
max=Math.max(temp[i], max);
}
System.out.println(max);
}
【改進】考慮到在計算每個temp[i]時都要找到最大的,由于數組無序,是以每次都需要順序查找。可以讓數組有序那麼就可以使用二分查找,進而算法複雜度就可以降到O(NlogN)。可以采用一個數組存儲最大遞增子序列的最末元素:即: B[ temp[j] ]= aj。
在數組B中用二分查找法找到滿足j<i且B[f(j)]=aj<ai的最大的j,并将B[f[j]+1]置為ai。
//O(NlogN)解法
public void longestIncreasingSubsequence(int[] a){
/*
* 在計算每一個f(i)時,都要找出最大的f(j)(j<i)來,由于f(j)沒有順序,隻能順序查找滿足aj<ai最大的f(j),
* 如果能将讓f(j)有序,就可以使用二分查找,這樣算法的時間複雜度就可能降到O(nlogn)。
* 于是想到用一個
* 數組B來存儲“子序列的”最大遞增子序列的最末元素,
* 即有B[f(j)] = aj
* 在計算f(i)時,在數組B中用二分查找法找到滿足j<i且B[f(j)]=aj<ai的最大的j,并将B[f[j]+1]置為ai。
*/
int[] temp=new int[a.length+1];
temp[0]=-100;
temp[1]=a[0];
int Len=1;
int p,r,m;//p,r,m分别為二分查找的上界,下界和中點;
for(int i = 1;i<a.length;i++)
{
p=0;r=Len;
while(p<=r)//二分查找最末元素小于ai+1的長度最大的最大遞增子序列;
{
m = (p+r)/2;
if(temp[m]<a[i]) p = m+1;
else r = m-1;
}
temp[p] = a[i];//将長度為p的最大遞增子序列的目前最末元素置為ai+1;
if(p>Len) Len++;//更新目前最大遞增子序列長度;
}
System.out.println(Len);
}
【TreeSet解法】treeSet底層是使用紅黑樹實作,是以可以按照值的升序進行排序。
set.ceiling(i)傳回set集合中比i大的最小元素。
public int lengthOfLIS2 (int[] nums) {
/*
* TreeSet是一個有序集合,TreeSet中的元素将按照升序排列,預設是按照自然排序進行排列,
* 意味着TreeSet中的元素要實作Comparable接口。或者有一個自定義的比較器。
* 我們可以在構造TreeSet對象時,傳遞實作Comparator接口的比較器對象。
*/
TreeSet<Integer> set = new TreeSet<>();
for(int i : nums) {
//Returns the least element in this set greater than or equal to the given element,
//or null if there is no such element.
Integer ceil = set.ceiling(i);
if(null != ceil) {
set.remove(ceil);
}
set.add(i);
}
return set.size();
}
【問題2】最長不重複子串問題
【問題描述】Given a string, find the length of the longest substring without repeating characters.
搜尋過程如下:記錄上一次最長子串起始位置last,然後進行下一次搜尋。比較得到最長不重複子串
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIyVGduV2QvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LcZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39jNyYjN1cDM2ETMxUDM2EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
public int lengthOfLongestSubstring(String s) {
if(s.length()==0||s.length()==1)
return s.length();
char[] sArr=s.toCharArray();
int last=0;
int result=-1;
int[] dp=new int[sArr.length];
dp[0]=1;
for(int i=1;i<sArr.length;i++){
for(int j=i-1;j>=last;j--){
if(sArr[i]==sArr[j]){
last=j+1;//更新上一次最長子串起始位置
dp[i]=i-j;//最長不重複子串
break;
}else if(j==last){
dp[i]=dp[i-1]+1;//都不重複則更新最長不重複子串
}
}
result=Math.max(dp[i], result);
}
return result;
}
【問題3】兩個序列的最長公共子序列
既然是經典的題目肯定是有優化空間的,并且解題方式是有固定流程的,這裡我們采用的是矩陣實作,也就是二維數組,用來LCS的長度。
第一步:先計算最長公共子序列的長度。
第二步:根據長度,然後通過回溯求出最長公共子序列。
現有兩個序列X={x1,x2,x3,...xi},Y={y1,y2,y3,....,yi},
設一個C[i,j]: 儲存Xi與Yj的LCS的長度。
遞推方程為:
//最長公共子序列
public int LCS(int[] a,int[] b){
int[][] temp=new int[a.length+1][b.length+1];
int result=0;int dp=0;
for(int i=1;i<=a.length;i++)
temp[i][0]=0;
for(int j=0;j<=b.length;j++)
temp[0][j]=0;
for(int k=1;k<=a.length;k++){
for(int l=1;l<=b.length;l++){
if(a[k-1]==a[l-1])
temp[k][l]=temp[k-1][l-1]+1;
else if(temp[k][l-1]<=temp[k-1][l])
temp[k][l]=temp[k][l-1];
else
temp[k][l]=temp[k-1][l];
result=Math.max(temp[k][l], result);
}
}
return result;
}
動态規劃的一個重要性質特點就是解決“子問題重疊”的場景,可以有效的避免重複計算,根據上面的公式其實可以發現C[i,j]一直儲存着目前(Xi,Yi)的最大子序列長度。
【總結】以上就是常見動态規劃問題,關鍵就是把問題分解為若幹子問題,找到決策條件,然後進行更新,進而得到問題的最優解。