动态规划整理

1.最长连续序列。比如  abccccfa,最长连续序列为cccc，长度为4

思路：另开一个数组记录到目前位置最长连续序列长度。每个位置的字符（除第一个）和前一个比较，相同+1，不同标为1

图示：

代码：

#include 
#include <string.h>
int main()
{char s[10] = "abccccfa";int num[10] = { 0};char tmp;int maxpos, maxval, i;num [0] = 1;maxpos = 0;tmp = s[0];for(i = 1; i ){if (s[i] == tmp)num[i] = num[i-1] + 1;elsenum[i] = 1;if(num[i] > num[maxpos])maxpos = i;tmp = s[i];}printf("maxlen:%d***maxchar:%c
", num[maxpos], s[maxpos]);return 0;
}

结果：

分析： 空间复杂度：O(n)  时间复杂度：O(n)

同思路问题：

（1）求一字母序列的最长连续上升序列的长度（比如abcffgmnE，abc长为3）

    思路：构造一同样大小的数组来记录到目前为止的最长连续序列的长度。在确定该位置的长度是，和前一个比较，如果ascii吗相减为1，那么在上一个长度的基础上+1；否则直接赋值1。

（2）求数字序列的最长连续上升序列的和（比如34123480，1234和为10）

    思路：构造一同样大小的数组来记录到目前为止的最长连续序列的和。在确定该位置的和是，和前一个比较，如果相差1，那么在上一个和的基础上+该位置原数组的值；否则直接复制该位置原数组的值。

（3）数列中最大连续元素之和（比如：3 -2 5 1 -10，最大元素之和为7（3 -2 5 1））

int MaxSubSum(int *arr,int n)
{int tmp = 0;int MAX = arr[0];for(int i = 0 ; i < n ; i++){tmp += arr[i];if(tmp < 0){tmp = 0;}if(MAX < tmp){MAX = tmp;}}return MAX;

 

2.最大上升序列的长度 （如：“amnpabpzjoq” 的最大上升序列 为："amnpz" 长度为5）

图示：

代码：

#include 
#include 
int main()
{char s[] = "amnpabpzjoq";int num[100] = {0};int maxnum, i, j;for(i = 0; i < strlen(s); i++){maxnum = -1;for(j = i-1; j >=0; j--){if (s[i] > s[j] && num[j] > maxnum)maxnum = num[j];}if (maxnum == -1)num[i] = 1;elsenum[i] = maxnum + 1;}maxnum = num[0];for (i = 1; i < strlen(s); i++){printf("%d
", num[i]);if (num[i] > maxnum)maxnum = num[i];}printf("maxlen:%d
", maxnum);
}

结果：

  3. 编辑距离

定义：字符串a只能通过“替换、插入、删除”三种操作得到字符串b，期间所做操作的次数。

例如：abc ——> cb，编辑距离为2。执行的操作：a替换为c，删除字符c.

思路：二维数组记录到字符a的m位置和字符串b的n位置，编辑距离f(m, n)。

       f(m, n) = min(f(m-1, n)+1, f(m, n-1)+1, f(m-1, n-1)+same(m, n))， 其中same(m,n)指字符串a的第m个字符是否等于字符串b的第n个字符，等为0，否则为1.

注意： 空和字串的相似程度时，距离为别的字串的长度！

图示：

代码：

#include 
#include <string.h>
int minvalue(int a, int b, int c)
{int min = a > b ? b : a;min = min > c ? c : min;return min;
}
int same(int a, int b)
{if (a != b)return 1;else return 0;
}
int main()
{char a[] = "bca";char b[] = "abc";int lena = strlen(a);int lenb = strlen(b);int c[lena+1][lenb+1], i, j;for(i=0; i <= lena; i++)c[i][0] = i;    for(i=0; i <= lenb; i++)c[0][i] = i;for(i = 1; i <= lena; i++)for(j=1; j <= lenb; j++)c[i][j] = minvalue(c[i-1][j]+1, c[i][j-1]+1, (c[i-1][j-1]+same(a[i], b[j])));for(i=0; i <= lena; i++){for(j=0; j <= lenb; j++)printf("%d	", c[i][j]);printf("
");}printf("Lavenshtein distance:%d
", c[lena][lenb]); return 0;
}

执行结果：

同思路问题：

1.最长公共子序列：详见：http://www.cnblogs.com/kaituorensheng/archive/2013/03/31/2992319