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;
}