荒废算法的学习已经快一年了，最近越来越认识到算法的重要性，虽然可能不去参加ACM比赛，但是算法也是一个程序员必备的一门课。让我有点难受是过去所学得算法似乎都没有真正地去搞懂过，有很多细节的地方都是以自己的想法掩盖过去，试图说服自己已经懂了，所以在算法的学习路上才会那么的坎坷（当然我现在仍然在算法学习路上）。其实很多时候都怕自己学算法不会变通，生搬硬套，也许是自己不够熟悉，练习不够。但不管如何，继续摸索。
昨天学习了动态规划的最长公共子序列问题。评判一个问题是否可以用
动态规划去解决时，需要判断该问题是否具有以下的两个特点。
- 最优子结构。最优子结构是指一个问题可以分解为若干的子问题，二这些子问题在结构上是与原问题一致的，只是问题的规模会越来越小。
- 重叠子问题。在一个问题被分解为若干的子问题后，可能会出现重叠的子问题，即一个问题会被求解多次，浪费资源。重叠子问题的解决可以使用数组去保存子问题的结果，当问题再次被分解为子问题时先判断该子问题是否已经被计算过了，如果被计算过就无须再次计算，直接使用子问题的结果。
最长公共子序列问题的分析。
1.首先子序列可以是不连续的，比如字符串 ABCDE是一个序列，而 ACE是该字符串的子序列，ACE并没有相邻。
2. 以C[i] [j] 作为长度为i的字符串A和长度为j的字符串B的最长公共子序的长度。假设A[i]为字符串A的第i个元素，B[j]为字符串B的第j个元素.
3. 当A[i]==B[j]时， 此时他们的公共子序列的长度为A[i-1]和B[i-1]时候的最长公共子序列的长度加1，即C[i][j]=c[i-1][j-1].
4. 当A[i]!=B[j]时,需要判断以下三种情况：
（1）A[i]等于B[0]~B[j-1]中的一个，即A[i]对于最长公共子序列有贡献,此时的最长公共子序列的长度为 c[i][j-1]
（2）B[j]等于A[0]~A[i-1]中的一个,即B[i]对于最长公共子序列有贡献.此时的最长公共子序列的长度为 c[i-1][j]
（3）A[i]不等于B[0]~B[j-1]中的一个， B[j]不等于A[0]~A[i-1]中的一个 ，即A[i]和B[j]对于最长公共子序列的长度都没有贡献.此时的最长公共子序列的长度为 c[i]-1[j-1].
显然第一种情况的最长公共子序列长度都比第三种的大，所以我们只要考虑前两者，且要取两者中较大的一个。因此我们得到了该最长公共子序列的递推方程组。
我们可以通过递归不断地去分解问题。
也可以从子问题出发，把子问题计算出来，再去解决父问题，将子问题的求解结果保存到数组，下次便可以直接使用，同时无需去判断子问题是否已经解决过，因为是从子问题出发的。
这里我们使用了第二种方法
先考虑从c[0][j]和c[i][0]的问题，A串或B串长为0时，其最长公共子序列的长度为0，因此需要初始化为0；
这里c[i][j]的行和列都加了一，因为需要保存AB串长度为0时候其最长公共子序列的长度。
最长公共子序列代码
//fun为二维数组实现
//fun1为滚动数组实现
#include <stdio.h>
#define m 100
#define n 100
int c[m+1][n+1]={
0};//c[m][n]为长度为m的A的子序列与长度为n的B的子序列的最长公共子序列
//思路：
//如果xi=xj，则最长公共子序列为c[i-1][j-1]+1
//图个xi!=xj,xi最长公共子序列为
void init(){
//长度为0的序列与另外一条序列的最长公共子序列为0
for (int i=0;i<=m;i++)
c[i][0]=0;
for (int j=0;j<=n;j++)
c[0][j]=0;
}
char A[m]="ABCDEFGCC";
char B[n]="CREFYSDJNHGCCS";
/*动态规划，非递归，因为是自下而上的，先计算了子问题，在往上计算大的问题 *因为一开始就对最小子问题有了初始化（init函数），每次的计算都需要用到上次计算的结果， *故用数组保存上次的结果，下次便可以直接使用 */
//程序的编写需要注意的是数组长度问题，
int max(int a,int b){
return a>b?a:b;
}
int fun(int i,int j){
if(A[i]==B[j]){
//c数组行和列都是比AB数组长度多一的
//因为AB两序列数组下标为0其长度为1而不是0
//所以c数组行和列增加一来保存AB序列长度为0时候的其最长公共子序列的长度
//也就是init函数的所要做的操作
c[i+1][j+1]=c[i][j]+1;
}else{
c[i+1][j+1]=max(c[i][j+1],c[i+1][j]);
}
return c[i+1][j+1];
}
//滚动数组
int c1[2][n]={
0};//c1选择为较小的子序列长度
int fun1(int i,int j){
if(A[i]==B[j]){
//判断两序列元素是否相等
//c1数组长度是比AB数组长度多一的
//因为AB两序列数组下标为0其长度为1而不是0
//所以c1数组增加一来保存AB序列长度为0时候的其最长公共子序列的长度
c1[(i+1)%2][j+1]=c1[i%2][j]+1;
}else{
c1[(i+1)%2][j+1]=max(c1[(i+1)%2][j],c1[(i)%2][j+1]);
}
}
void common(int lm,int ln){
//普通二维数组来保存最长公共子序列长度
printf("%s\n", "common method result:");
for(int i=0;i<lm;i++)
for(int j=0;j<ln;j++){
fun(i,j);//fun是动态规划算法的具体实现
printf("%d ",c[i][j] );
if(j==ln-1){
printf("\n");
}
}
printf("%d\n lm:%d ln:%d",c[lm][ln],lm,ln);//输出AB数组的长度以及c[m][n]的值
}
//由于在使用二维数组进行动态规划时，
//每次使用到的数据只有前一个和上一行的数据
//因此可以使用一行数组进行滚动，从而缩小空间
void roll(int lm,int ln){
//滚动数组来保存最长公共子序列长度
printf("\n%s\n", "roll method result:");
printf("lm :%d\n", lm);
for(int i=0;i<lm;i++){
for (int j=0;j<ln;j++){
//fun1是动态规划算法的具体实现
fun1(i,j);
//把j作为列，i为行；选择AB两序列中长度较短的保存；这里并没有加判断语句进行选择
//
}
// printf("\n");
// for (int j=0;j<ln;j++){
// printf("%d ",c1[i%2][j] );
// }
// printf("\n");
// for (int j=0;j<ln;j++){
// printf("%d ",c1[(i+1)%2][j] );
// }
// printf("\n");
}
printf("\n");
for(int i=0;i<=ln;i++){
printf("%d ", c1[lm%2][i]);//最后输出第lm%2的数组（因为长度为lm)
}
}
int main(){
init();
int lm=0,ln=0;
while(A[lm]!='\0'){
lm++;
}
while(B[ln]!='\0'){
ln++;
}
common(lm,ln);//二维数组实现
roll(lm,ln);//滚动数组实现
return 0;
}
另外的最长公共子串的问题跟最长公共子序列其实是差不多的，最长公共子串是相邻的，需要在判断A[i] 和B[i]不等的时候
附上最长公共子串的代码，可能实现有点出入
#include <stdio.h>
#define m 100
#define n 100
int c[m+1][n+1]={
0};
void init(){
for (int i=0;i<=m;i++)
c[i][0]=0;
for (int j=0;j<=n;j++)
c[0][j]=0;
}
char A[m]="ABCDEFG";
char B[n]="BCACDEFGCA";
int max(int a,int b){
return a>b?a:b;
}
int fun(int i,int j){
if(A[i]==B[j]){
c[i+1][j+1]=c[i][j]+1;
}else{
c[i+1][j+1]=0;
}
return c[i][j];
}
int main(){
init();
int lm=0,ln=0;
while(A[lm++]!='\0'){
}
while(B[ln++]!='\0'){
}
for(int i=0;i<lm-1;i++)
for(int j=0;j<ln-1;j++){
fun(i,j);
//printf("%d\n",c[i][j] );
}
int maxn=0;
for (int i=0;i<lm;i++){
for (int j=0;j<ln;j++){
if(maxn<c[i][j]) maxn=c[i][j];
printf("%d ", c[i][j]);
if(j==ln-1){
printf("\n");
}
}
}
printf("%d\n lm:%d ln:%d \n%s",maxn,lm,ln,B);
return 0;
}
算法学习路途遥远，一点一点积累。。。。。
京公网安备 11010502036488号