编号问题

(1) 最长非降子序列（LIS）

【问题描述】一个序列 a1，a2，a3，…，an 共 N 个元素。现在请用动态规划的方法求出从序列找到一个长度最长、且前面一项不大于它后面任何一项的子序列。只需输出序列的长度。N≤1000。

【分析】

1. 递推思路：f(i)表示对于前 i 个数组成的序列，保留第 i 个数时能取得的非降子序列的最大长度。

2. 状态转移方程：f(i)＝max{f(j)}＋1（aj＞ai 且 i＞j）

int f[1000]; int LIS(int *a, int n) {  int max, k;

f[0]=0;  for (int i=1;i<=n;i++) {   max=k=0;   for (int j=i-1;j>0;j--)    if ((a[j]<a)&&(f[j]>=max)) max=f[j], k=j;   f=f[k]+1; }    max=0; for (int i=1;i<=n;i++) if (f>max) max=f;  return max; }

(2) 最长公共子序列（LCS）

【问题描述】有两个序列 a 和 b。求一个最长的序列 p，使它既是 a 的子序列，又是 b 的子序列。输出序列 p 的长度。（a、b 长度小于1000）

【分析】

1. 状态表示：f(i,j)表示 a 的前 i 个元素、b 的前 j 个元素中最长公共子序列的长度。

ìïf(i－1,j)

2. 状态转移方程：f(i,j)＝maxíf(i,j－1)  

ïîf(i－1,j－1)＋(ai==bj?1:0)

int f[1001][1001]; int LCS(int *a, int m, int *b, int n)   // a中m个元素，b中n个元素 {  memset(f,0,sizeof(f));  for (int i=1; i<=m; i++)   for (int j=1; j<=n; j++)   {    if (a==b[j]) f[j]=f[i-1][j-1]+1;    f[j] = max(f[j], max(f[i-1][j], f[j-1]));   } return f[m][n]; }