1. 設計一個O（n的平方）時間的演算法，找出由n個數組成的序列的最長單調遞增子序列
用冒泡法 時間復雜度=O(n^2)
以 下是c語言版
#include <stdio.h>
main()
{int a[10];
int i,c,j;
for(i=0;i<10;i++)
{printf("請輸入十個數,這是第%d個:",i+1);
scanf("%d",&a[i]);
}
for(i=0;i<10;i++)
{
for(j=10;j>i+1;j--)
{if(a[j-1]<a[j-2])
{c=a[j-1];
a[j-1]=a[j-2];
a[j-2]=c;
}
}
}
printf("從小到大的順序是:");
for(i=0;i<10;i++)
{printf("\n%d",a[i]);
}
getch();
}
2. 用動態規劃方法找出由n個數a【i】（1<=i<=n）組成的序列的一個最長單調遞增子序列
f(i)=max{f(j)+1},c[i]=j(f(j)+1{max}),其中j<i and a[j]<a[i]
f(i)表示若第i個數為最長遞增子序列的末端,此時的最長遞增子序列的長度
c[i]表示令f(i)最大的前一個元素
用這種方法可以找到最大的f(i),通過c[i]的倒推可以得到最長單調遞增子序列
因為對每一個元素找到f(i)的效率為O(i),所以對所有元素找到的時間效率為O(n^2),空間效率為O(3n)
優化:
要能更改f(i)需要兩個條件：
j<i and a[j]<a[i]
f(j)盡可能大
以上兩個條件提示我們後面的值一定要大於前面的值。因帆模塵此我們試著構建一個遞增的序列。在這個遞增的序列中查找可碼老以更改的f值,使得序列的值盡可能小。
舉例:
有序列
1,5,6,2,3,4,8,5
令d[i]表示f(j)=i中的數中最小的那個的序號
我們有如下的處理
初始:d={}
1:d={1}
2:d={1,2}
3:d={1,2,3}
4:d={1,4,3} (這里:f(4)=f(2)=2,但是a[4]<a[2],如果後面有某個數要作為第三大的數的話,小一點的a[4]顯然更有優勢)
5:d={1,4,5}
6:d={1,4,5,6}
7:d={1,4,5,6,7}
8:d={1,4,5,6,8}
同樣的，在替換或加到序列最後一個之前，存下d-1
這樣就可以通過態禪序列d的最後一項向前倒推到整個序列
因為序列d有序，可以通過二分搜索得到，因此時間效率為O(nlogn),空間效率為O(3n)
3. 設A是由n個不同整數構成的序列，設計演算法求A中最長的單調遞增子序列
#include <vector>
using namespace std;
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
vector<int> p(a.size());
int u, v;
if (a.empty()) return;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++)
{
// If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
// Binary search to find the smallest element referenced by b which is just bigger than a[i]
// Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
for (u = 0, v = b.size()-1; u < v;)
{
int c = (u + v) / 2;
if (a[b[c]] < a[i]) u=c+1; else v=c;
}
// Update b if new value is smaller then previously referenced value
if (a[i] < a[b[u]])
{
if (u > 0) p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
/* Example of usage: */
#include <cstdio>茄差
int main()
{
int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
vector<顫腔皮int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
vector<int> lis; //圓游 lis : Vector containing indexes of longest subsequence
find_lis(seq, lis);
//Printing actual output
for (size_t i = 0; i < lis.size(); i++)
printf("%d ", seq[lis[i]]);
printf("\n");
return 0;
}
4. 動態規劃如何去找動態轉移方程
1、最長公共子串
假設兩個字元串為str1和str2，它們的長度分別為n和m。d[i][j]表示str1中前i個字元與str2中前j個字元分別組成的兩個前綴字元串的最長公共長度。這樣就把長度為n的str1和長度為m的str2劃分成長度為i和長度為j的子問題進行求解。狀態轉移方程如下：
dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])
dp[i][j] = 0; (str1[i] != str2[j])
因為最長公共子串要求必須在原串中是連續的，所以一但某處出現不匹配的情況，此處的值就重置為0。
詳細代碼請看最長公共子串。
2、最長公共子序列
區分一下，最長公共子序列不同於最長公共子串，序列是保持子序列字元串的下標在str1和str2中的下標順序是遞增的，該字元串在原串中並不一定是連續的。同樣的我們可以假設dp[i][j]表示為字元串str1的前i個字元和字元串str2的前j個字元的最長公共子序列的長度。狀態轉移方程如下：
dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i-1] == str2[j-1])
dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (str1[i-1] != str2[j-1])
詳細代碼請看最長公共子序列。
3、最長遞增子序列（最長遞減子序列）
因為兩者的思路都是一樣的，所以只給出最長遞減子序列的狀態轉移方程。假設有序列{a1,a2,...,an}，我們求其最長遞增子序列長度。按照遞推求解的思想，我們用F[i]代表若遞增子序列以ai結束時它的最長長度。當 i 較小，我們容易直接得出其值，如 F[1] = 1。那麼，如何由已經求得的 F[i]值推得後面的值呢？假設，F[1]到F[x-1]的值都已經確定，注意到，以ax 結尾的遞增子序列，除了長度為1的情況，其它情況中，ax都是緊跟在一個由 ai(i < x)組成遞增子序列之後。要求以ax結尾的最長遞增子序列長度，我們依次比較 ax 與其之前所有的 ai(i < x)， 若ai小於 ax，則說明ax可以跟在以ai結尾的遞增子序列之後，形成一個新的遞 增子序列。又因為以ai結尾的遞增子序列最長長度已經求得，那麼在這種情況下，由以 ai 結尾的最長遞增子序列再加上 ax 得到的新的序列，其長度也可以確定，取所有這些長度的最大值，我們即能得到 F[x]的值。特殊的，當沒有ai(i < x)小 於ax， 那麼以 ax 結尾的遞增子序列最長長度為1。 即F[x] = max{1,F[i]+1|ai<ax && i<x}。
詳細代碼請看最長遞增子序列。
4、最大子序列和的問題
假設有序列{a1,a2,...,an}，求子序列的和最大問題，我們用dp[i]表示以ai結尾的子序列的最大和。
dp[1] = a1; (a1>=0 && i == 1)
dp[i] = dp[i-1]+ai; (ai>=0 && i>=2)
dp[i] = 0; (dp[i-1] + ai <=0 && i>=2)
詳細代碼請看最大子序列的和。
5、數塔問題（動態搜索）
給定一個數組data[n][m]構成一個數塔求從最上面走到最低端經過的路徑和最大。可以假設dp[i][j]表示走到第i行第j列位置處的最大值，那麼可以推出狀態轉移方程：
dp[i][j] = max{dp[i-1][j-1],dp[i-1][j]} + data[i][j];
View Code
6、（01）背包問題
這是一個經典的動態規劃問題，另外在貪心演算法里也有背包問題，至於二者的區別在此就不做介紹了。
假設有N件物品和一個容量為V的背包。第i件物品的體積是v[i]，價值是c[i]，將哪些物品裝入背包可使價值總和最大？
每一種物品都有兩種可能即放入背包或者不放入背包。可以用dp[i][j]表示第i件物品放入容量為j的背包所得的最大價值，則狀態轉移方程可以推出如下：
dp[i][j]=max{dp[i-1][j-v[i]]+c[i],dp[i-1][j]};
View Code
可以參照動態規劃 - 0-1背包問題的演算法優化、動態規劃-完全背包問題、動態規劃-多重背包問題
7、矩陣連乘（矩陣鏈問題）-參考《演算法導論》
例如矩陣鏈<A1,A2,A3>,它們的維數分別為10*100,100*5,5*50，那麼如果順序相乘即((A1A2)A3)，共需10*100*5 + 10*5*50 = 7500次乘法，如果按照(A1(A2A3))順序相乘，卻需做100*5*50 + 10*100*50 = 75000次乘法。兩者之間相差了10倍，所以說矩陣鏈的相乘順序也決定了計算量的大小。
我們用利用動態規劃的方式(dp[i][j]表示第i個矩陣至第j個矩陣這段的最優解,還有對於兩個矩陣A(i,j)*B(j,k)則需要i*j*k次乘法)，推出狀態轉移方程：
dp[i][j] = 0; (i ==j，表示只有一個矩陣，計算次數為0)
dp[i][j] = min{dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]}; (i<j && i<=k<j)
dp[1][n]即為最終求解.
View Code
5. 設計一個O（n^2）時間的演算法，找出由n個數組成的序列的最長單調遞增子序列。
#include<槐帆iostream>
#include<ctime>
using namespace std;
#define N 10
void LCSL(int m,int n,int *x,int *y,int **c,int **b);//計算最長公共子序列長度。
void LCS(int i,int j,int *x,int **b);//根據b[i][j]的內容列印a,x數組的最長公鉛辯雹共子序列。
void QuickSort(int a[],int p,int r);//快速排序。
int Partition(int a[],int p,int t);//數組劃分，灶鬧將小於等於x的元素移到x左邊，大於x的元素移到x右邊。
void Swap(int &x,int &y);//交換元素x和y。
void LCSL(int m,int n,int *x,int *y,int c[][N],int b[][N])
{
c[0][0]=0;
int i,j;
for(i=1;i<=m;i++)
c[i][0]=0;
for(i=1;i<=n;i++)
c[0][i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
cout<<c[m][m]<<endl;
}
void LCS(int i,int j,int *x,int b[][N])
{
if(i==0||j==0) return;
if(b[i][j]==1)
{
LCS(i-1,j-1,x,b);
for(int y=1;y<i;y++)
if(x[y]==x[i])
return;
cout<<x[i]<<" ";
}
else if(b[i][j]==2)
{
LCS(i-1,j,x,b);
}
else
LCS(i,j-1,x,b);
}
void QuickSort(int a[],int p,int r)
{
if(p<r)
{
int q=Partition(a,p,r);
QuickSort(a,p,q-1); QuickSort(a,q+1,r);
}
}
int Partition(int a[],int p,int r)
{
int i=p,
j=r+1;
int x=a[p];
while(true)
{
while(a[--j]>x);
while((i<j)&&a[++i]<x);
if(i>=j)break;
Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
void Swap(int &x,int &y)
{
int t;
t=x;
x=y;
y=t;
}
int main()
{
int *a,*x;
a=new int[N];
x=new int[N];
int b[N][N];
int c[N][N];
cout<<"Please Input 10 Numbers:"<<endl;
for(int i=1;i<N;i++)
{
cin>>a[i];
x[i]=a[i];
}
QuickSort(x,1,N-1);
LCSL(N-1,N-1,a,x,c,b);
LCS(N-1,N-1,a,b); return 0;
}
6. c++中怎麼求數組中最長的遞增序列
例如數組 data[]={-9,0,-3,-5,-1,-2}
最後求得最長遞增子序列的長度為 3 （-9，-3，-1），當然還有好祥逗幾種同種長度的遞增子序列的組合
核心演算法：
C++表示演算法如冊宴晌下：
// 求數組中最長遞增子序列
int Array::Max_Length_GoUp_stack(int *data,unsigned int const length)
{
// 異常輸入，ITJOB
if(data == NULL || length == 0)
{
cout<<"輸入異常 Max_Length_GoUp"<<endl; return="" 0;="州鋒" }="" 正常輸入="" else="" {="" 核心演算法，用工具棧去解決問題="" stack * S = new stack;
S->push(0);
unsigned int now = 0;
unsigned int result = 1;
while(S->empty() == false)
{
// 可以進棧
now ++;
if(now < length)
{
while(now < length)
{
if(data[now] > data[S->top()])
{
S->push(now);
}
now++;
}
// 更新結果
if(S->size() > result)
result = S->size();
}
// 出棧操作
else{
now = S->top();
S->pop();
}
}
// 返回結果
return result;
}
}
7. 最長上升子序列
最長上升子序列問題是各類信息學競賽中的常見題型，也常常用段敏來做介紹動態規劃演算法的引例，筆者接下來將會對POJ上出現過的這類題目做一個總結，並介紹解決LIS問題的兩個常用
演算法(n^2)和(nlogn).
問題描述:給出一個序列a1,a2,a3,a4,a5,a6,a7....an,求它的一個子序列陪顫（設為s1,s2,...sn），使得這個子序列滿足這樣的性質，s1<s2<s3<...<sn並且這個子序列的長度最長。輸出這個最長的長度。（為了簡化該類問題，我們將諸如最長下降子序列及最長不上升子序列等問題都看成同一個問題，其實仔細思考就會發現，這其實只是<符號定義上的問題，並不影響問題的實質）
例如有一個序列:1 7 3 5 9 4 8,它的最長上升子序列就是 1 3 4 8 長度為4.
演算法1(n^2):我們依次遍歷整個序列，每一次求出從第一個數到當前這個數的最長上升子序列，直至遍歷到最後一個數字為止，然後再取dp數組里最大的那個即為整個序列的最長上升子序列。我們用dp[i]來存放序列1-i的最長上升子序列的長度，那麼dp[i]=max(dp[j])+1,(j∈[1, i-1]); 顯然dp[1]=1,我們從i=2開始遍歷後面的元素即可。握亂枝
8. 設計一個O(n2)時間演算法,找出由n個數組成的序列的最長單調遞增子序列
演算法導論15.4-5 請給出一個O(n^2)時間的演算法，使之能找出一個n個數的序列中最長的單調遞增子序列。
這個題目是在動態規劃部分，此處顯然是要用到動態規劃。
我們知道可以使用動態規劃思想的問題的的兩個重要的特徵是具有最優子結構和重疊子問題。下面就來分析一下這個問題：
對於一個n個元素的序列nums，設其最長單調遞增子序列為Sm(n)（m為遞增子序列的長度），則對於Sm存在兩種情況：
1、如果nums[n]比Sm-1的最後一個元素大，則Sm由Sm-1加nums[n]組成
2、如果nums[n]小於等於Sm-1的最後一個元素，則Sm即為Sm-1
但是這樣考慮有問題，因為如果Sm-1的序列有多個，我們則應該每一個都與nums[n]考察，如果nums[n]比所有Sm-1的尾元素都小或相等，而Sm-2的序列中又存在尾元素小於nums[n]的序列，則我們應該如何選擇，Sm應該是多少？
Sm-1+nums[n]、Sm-1、Sm-2+nums[n]
所以之前的分析是有問題的，在長度相同的情況下，我們優先選擇包含nums[n]的序列作為Sm(n)，因為每一個新加入的元素都可能改變不同長度的遞增子序列，因此我們需要維護每一個遞增子序列以獲取最優。
這里的最優子結構就是n個元素的最長遞增子序列是從前n-1個元素結尾的遞增子序列中的一個或者再加上nums[n]，這裡面自然存在很多重疊子問題。
代碼如下：
/************************************************************************/
/* 演算法導論15.4-5
* 找出n個數的序列中最長的單調遞增子序列
* 利用動態規劃思想，時間復雜度為O(n^2)*/
/************************************************************************/
#include<iostream>
using namespace std;
void printSequence(int *b,int* nums,int last);
int main()
{
int n=8;
int nums[9]={0,1,7,8,9,2,3,4,5};
//b存儲當前元素所在遞增子序列中當前元素的前一個元素序號
//c存儲以當前元素結尾的遞增子序列長度
//last存儲當前元素為止的序列中最長遞增子序列的最後一個元素的序號
//maxLen存儲當前最長遞增子序列的長度
int b[9]={0},c[9]={0},last[9]={0},maxLen=0;
c[1]=1,last[1]=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<i;j++)
{
if(nums[j]<nums[i] && c[j]+1>c[i])
{
c[i]=c[j]+1;
b[i]=j;
last[i]=i;
maxLen=c[i];
}else if(c[j]>c[i]){
maxLen=c[j];
last[i]=last[j];
}
}
}
cout<<"原序列長度為"<<n<<"，如下："<<endl;
for (int i=1;i<=n;i++)
{
cout<<nums[i]<<" ";
}
cout<<endl<<"最長遞增子序列長度為"<<maxLen<<"，如下："<<endl;
printSequence(b,nums,last[n]);
cout<<endl;
return 0;
}
void printSequence(int *b,int* nums,int last)
{
if(b[last]>0)
printSequence(b,nums,b[last]);
cout<<nums[last]<<" ";
}
9. O(nlogn)最長遞增子序列演算法,如何輸出所求子序列
#include <iostream>
#include <algorithm>首宴
#include <vector>
using namespace std;
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int>者納銀 dp(nums.size(), INT_MAX);
vector<int> pos(nums.size(), INT_MAX);
for (int i = 0; i < nums.size(); i++){
pos[i] = lower_bound(dp.begin(), dp.end(), nums[i]) - dp.begin();
*lower_bound(dp.begin(), dp.end(), nums[i]) = nums[i];
}
int max_n = lower_bound(dp.begin(), dp.end(), INT_MAX) - dp.begin();
vector<int> res(max_n, -1);
int j = max_n - 1;
for (int i = nums.size() - 1; i >= 0; --i){
if (j < 0) break;
if (j == pos[i]){
res[j--] = nums[i];
}
}
for (auto x : res)
cout << x << " ";
cout << endl;
return max_n;
}
};
int main() {
Solution s;
vector<int> nums = {12,2, 34, 4, 5, 6, 7, 8, 9, 0};
cout << s.lengthOfLIS(nums) <<茄耐 endl;
return 0;
}
10. C語言，最長上升子序列數,,
最長上升子序列（LIS）
問題描述：設現在有一串序列，要求找出它的一串子序列，這串子序列可以不連續，但必須滿足它是嚴格的單調遞増的且為最長的。把這個長度輸出。
示例：1 7 3 5 9 4 8 結果為4
題例：參看POJ 2533
解法：
1. DP之O(n2)演算法：先按DP的思想來分析一下，要想求n個數的最長上升子序列，設有數據數組data[n]和狀態數組dp[n]，則對其尾元素data[n]來說，它的最長上升子序列就是它自己，即dp[n]=1，而當把它的前一個元素data[n-1]考慮進來時，如果data[n-1]<data[n]則會存在一個長度為2的上升子序列，如果data[n-1]>data[n]那麼這個長度仍會是1。當把這個思想一般化的時候，對於任意一個元素data[k]來說，我們需要找出在data[k]以後的元素中比data[k]大，並且最長的一個序列做為它的後繼。這樣dp[k]就可以寫成dp[k+1]+1。現在我們定義一個量dp[k]=m，它代表著到第k個元素為止（可以包含k也可以不包含k），它的最長上升序列的長度為m。仔細體會dp[k]=m的意義，這裡面的k是可包括在內，也可以不包括在內的（與之前的最大子序列和不同）。要想確定這個m的值，就必須找到一個在第k個元素之前的一個元素的值小於data[k]的值，並且那個元素所對應的dp值是找到的滿足第一個條件前提下dp值最大的一個。這就意味著我們需要內層遍歷之前算出來的dp值，所以需要兩層循環來實現這個演算法。這樣我們就可以總結出狀態轉移方程為dp[k]=max(dp[i](1<=i<=k&&a[i]<a[k])+1。其中找dp[i]的過程我們需要用一層循環來實現，而找dp[k]的過程也要一層循環，所以我們得到了O(n2)的演算法。
dp[k]=max(dp[i])+1 其中i滿足(1<=i<=k&&a[i]<a[k])
常式：
#include <stdio.h>
const int inf = -0x3fffffff;
int main(void)
{
int i,j,len,max,res,data[] = {1,7,3,5,9,4,8},dp[20]={1};
len = sizeof(data)/sizeof(int);
res = max = inf;
for(i=1;i<len;i++)
{
max = inf;
for(j=0;j<=i;j++)
if(data[i]>data[j]&&max<dp[j])
max=dp[j];
dp[i]=max+1;
if(res<dp[i])
res = dp[i];
}
printf("%d\n",res);
return 0;
}