動(dòng)態(tài)規(guī)劃的核心是狀態(tài)和狀態(tài)轉(zhuǎn)移方程
DAG(Directed Acyclic Graph)
DAG:有向無環(huán)圖
很多問題都可以轉(zhuǎn)化為DAG上的最長路，最短路，路徑計(jì)數(shù)問題
嵌套矩形
描述：有n個(gè)矩形，每個(gè)矩形可以用a,b來描述歪泳，表示長和寬锌妻。矩形X(a,b)可以嵌套在矩形Y(c,d)中當(dāng)且僅當(dāng)a<c,b<d或者b<c,a<d（相當(dāng)于旋轉(zhuǎn)X90度）。例如（1,5）可以嵌套在（6,2）內(nèi)匀泊，但不能嵌套在（3,4）中影暴。你的任務(wù)是選出盡可能多的矩形排成一行，使得除最后一個(gè)外探赫，每一個(gè)矩形都可以嵌套在下一個(gè)矩形內(nèi)型宙。
抽象為求DAG中不固定起點(diǎn)的最長路徑：
- 構(gòu)造圖（鄰接矩陣）：如果矩形A可以包含矩形B，則A有一條到B的路徑：A->B;
- 定義狀態(tài)dp[i]:表示從i出發(fā)的最長路長度
- 狀態(tài)轉(zhuǎn)移方程：dp[i] = max(d[j]+1 | （i,j)屬于邊集）)
湊硬幣
有面值為V1,V2,...,Vn的n種硬幣若干枚伦吠，如何用最少/最多的硬幣湊夠S元妆兑？
抽象為DAG中固定終點(diǎn)的最長路和最短路（下面以最長路敘述）
1.把每種面值看做一個(gè)點(diǎn)，表示“還需要湊足的面值”毛仪，起點(diǎn)（初始狀態(tài)）S,終點(diǎn)（目標(biāo)狀態(tài)）0.
2.定義狀態(tài)d（i）:表示從節(jié)點(diǎn) i 出發(fā)到 0 的 最長路搁嗓。//即湊足 i 需要的最多硬幣。
3.狀態(tài)轉(zhuǎn)移方程：d(i) = max{ d(i - Vj) + 1} ,i >= Vj箱靴。
背包問題
- 0-1背包問題
n種物品腺逛，每種只有一件，物品i質(zhì)量為w[i],價(jià)格為c[i],有一個(gè)容量為V的背包衡怀，如何挑選使背包里的物品總價(jià)值最大棍矛？
定義狀態(tài)：d[i][v] : 表示前i個(gè)物品填滿v的最大總價(jià)值。
狀態(tài)轉(zhuǎn)移方程：d[i][v] = max(d[i-1][v], d[i-1][v-w[i]]+c[i]);
邊界：d[0][v]=0;
- 完全背包問題
n種物品若干件抛杨，每種每件質(zhì)量為w[i],價(jià)格為c[i],有一個(gè)容量為V的背包够委，如何挑選使背包里的物品總價(jià)值最大？
和湊硬幣很像怖现，可以看成固定起點(diǎn)的帶權(quán)的DAG的最長路
定義狀態(tài)：d(i):i表示容量茁帽，d(i）為容量為i的最大價(jià)值。
狀態(tài)轉(zhuǎn)移方程：d(i)=max( d(i-w(j)) + c(j) ); i>=w(j) j=0,1,...,n-1
邊界：d(0)=0;
最大連續(xù)子序列和
描述：給定序列A比如[-1,2,3,4,-5,2],找出連續(xù)的和最大的子序列a[2,3,4];
(比如求最大連續(xù)積扒汀潘拨；或者不連續(xù)的最大和啊都是相同的思路)
定義狀態(tài)描述
dp[i]: 表示以A[i]結(jié)尾的最大連續(xù)子序列的和
狀態(tài)轉(zhuǎn)移方程：
dp[i]=max(dp[i-1]+A[i],A[i]);
邊界
dp[0]=A[0];
最長不下降子序列LIS
給定一個(gè)序列A，給定一個(gè)排序的標(biāo)準(zhǔn)（比如是降序）,找出A的一個(gè)最長的滿足這個(gè)排序的子序列饶号。
例：A=[3,3,4,5,1,2,9]=>最長子序列a=[3,3,4,5,9]
= = = =
狀態(tài)：
dp[i]铁追；//代表結(jié)尾是A[i]的最大子序列長度
狀態(tài)轉(zhuǎn)移方程：
dp[i] = max(1,dp[j]+1); for j=0,...,i-1
時(shí)間復(fù)雜度O(n^2)
可以提高到O(nlogn)
dp和二分查找（from這里)而且這個(gè)方法還構(gòu)造出了這個(gè)最長子序列（最有潛力遞增的），用dp數(shù)組就只是返回最長子序列的長度讨韭。
~ 構(gòu)建數(shù)組buildingList,返回buildlist.size()即所求最長子序列長度脂信。
buildingList[i]存的是長度為i的子序列的最后一個(gè)元素a癣蟋，這個(gè)元素a一定是小的透硝，也就是如果出現(xiàn)比a更小的，就要更新a（用二分查找疯搅，因?yàn)閎uildinglist一定是嚴(yán)格單調(diào)遞增的）
比如給一個(gè)序列[6,2,4,3]
1.buildingList[0]=6;//6
2. **2<6**->buildingList[0]=2;//2
3. **4>2**->buildingList[1]=4;//2 4
4. **3>2;3<4**->buildingList[1]=3;//2 3----二分法返回返回第一個(gè)大于等于3的位置i
->return buildingList.size()=2;//最長升序子序列長度為2
題目：
最大公共子序列LCS
描述：給定兩個(gè)字符串A,B,求這兩個(gè)字符串公共部分的最長長度（不用連續(xù)）
~例 “ate” and "delete" -> "te"為公共子串濒生，長度為2~
LCS描述：
string1,string2長度分別為m,n
構(gòu)建二維數(shù)組dp[m+1][n+1];
定義狀態(tài)dp[i][j]: 表示string1'(下標(biāo)為0,...,i-1)和string2'(下標(biāo)為0,...,j-1)的最長公共子串的長度。
狀態(tài)轉(zhuǎn)移方程：
int LCS(string word1,string word2){
int m=word1.length();
int n=word2.length();
//int dp[m+1][n+1];
vector<vector<int> > dp(m+1,vector<int>(n+1));
//初始化一下dp二維數(shù)組（邊界）
for(int i=0;i<=m;i++){
dp[i][0]=0;
}
for(int i=0;i<=n;i++){
dp[0][i]=0;
}
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i == 0 || j==0)
continue;
//狀態(tài)轉(zhuǎn)移方程
if(word1[i-1] == word2[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[m][n];
}
題目
delete-operation-for-two-strings
最長回文子串
描述：給一個(gè)字符串A幔欧，比如“ababb”,那么最長回文子串有“aba”,"bab"罪治；
動(dòng)態(tài)規(guī)劃解決方法(from here) ：
定義狀態(tài)的指標(biāo)函數(shù)：p[i][j]:
字符子串A[i]到A[j]是否是回文丽声；是則為1，否則為0觉义；
狀態(tài)轉(zhuǎn)移方程：
邊界
復(fù)雜度
時(shí)間復(fù)雜度為O(n^2);
空間復(fù)雜度為O(n^2);// 空間復(fù)雜度可降低到O(1)
提高：
二分法+Hash->Time Complexity:O(nlogn);
Manacher's Algorithm->O(n)
class Solution {
public:
string longestPalindrome(string s) {
int len=s.length();
int max=1;
int start[len]={-1};//儲(chǔ)存回文起點(diǎn)坐標(biāo)雁社，長度為max
int dp[len][len]={0};//dp[i][j]表示i,j之間是否是回文，回文是1晒骇，否則是0
//初始化邊界
for(int i=0;i<len;i++){
dp[i][i]=1;
start[i]=max;
if(i<len-1){
if(s[i]==s[i+1]){
dp[i][i+1]=1;
max=2;
start[i]=max;
}
}
}
for(int k=3;k<=len;k++){//k為子串長度
for(int i=0;i<len+1-k;i++){//j-i+1=k j<len->i<len+1-k
int j=k+i-1;
if(s[i]==s[j]&&dp[i+1][j-1]==1){
dp[i][j]=1;
max=k;
start[i]=max;//存了max的start[i]
}
}
}
int beginPos=0;
for(int i=0;i<len;i++){
if(start[i]==max){
beginPos=i;
break;
}
}
return s.substr(beginPos,max);
}
};
題目
longest-palindromic-substring
練習(xí)
from PAT
/*1045 Favorite Color Stripe (30)（30 分）*/
/*最長不下降子序列 */
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
#define maxL 10000
int HashTable[maxL];
int Lcolor(vector<int> &stripe);
int main()
{
int colorsN, loveC, stripeC;
cin >> colorsN >> loveC;
int x;//暫存輸入的數(shù)
memset(HashTable, -1, sizeof(HashTable));
for (int i = 0; i<loveC; i++) {
cin >> x;
HashTable[x] = i;
}
cin >> stripeC;
vector<int> stripe;
for (int i = 0; i<stripeC; i++) {
cin >> x;
if (HashTable[x] != -1) {
stripe.push_back(x);//不是喜歡的顏色就不放進(jìn)stripe里了
}
}
cout << Lcolor(stripe);
return 0;
}
int Lcolor(vector<int> &stripe)
{
int n = stripe.size();
int *dp = new int[n];//用來存以strip[i]結(jié)尾的LIS值
int re = 0;
for (int i = 0; i<n; i++) {//狀態(tài)轉(zhuǎn)移方程
dp[i] = 1;
int tmpi = HashTable[stripe[i]];
for (int j = 0; j<i; j++) {
//如果h[j]<h[i]霉撵，并且dp[i]<dp[j]+1->dp[i]=dp[j]+1;
int tmpj = HashTable[stripe[j]];
if (tmpj <= tmpi && dp[i]<dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
re = max(re, dp[i]);
}
return re;
}
