1.最長連續(xù)序列。比如? abccccfa,最長連續(xù)序列為cccc，長度為4

思路：另開一個(gè)數(shù)組記錄到目前位置最長連續(xù)序列長度。每個(gè)位置的字符（除第一個(gè)）和前一個(gè)比較，相同+1，不同標(biāo)為1

圖示：

代碼：

#include <stdio.h> #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 <strlen(s); 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\n", num[maxpos], s[maxpos]);return 0; }

結(jié)果：

分析： 空間復(fù)雜度：O(n)? 時(shí)間復(fù)雜度：O(n)

同思路問題：

（1）求一字母序列的最長連續(xù)上升序列的長度（比如abcffgmnE，abc長為3）

? ? 思路：構(gòu)造一同樣大小的數(shù)組來記錄到目前為止的最長連續(xù)序列的長度。在確定該位置的長度是，和前一個(gè)比較，如果ascii嗎相減為1，那么在上一個(gè)長度的基礎(chǔ)上+1；否則直接賦值1。

（2）求數(shù)字序列的最長連續(xù)上升序列的和（比如34123480，1234和為10）

? ? 思路：構(gòu)造一同樣大小的數(shù)組來記錄到目前為止的最長連續(xù)序列的和。在確定該位置的和是，和前一個(gè)比較，如果相差1，那么在上一個(gè)和的基礎(chǔ)上+該位置原數(shù)組的值；否則直接復(fù)制該位置原數(shù)組的值。

（3）數(shù)列中最大連續(xù)元素之和（比如：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; View Code

?

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

圖示：

代碼：

#include <stdio.h> #include <string.h> 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\n", num[i]);if (num[i] > maxnum)maxnum = num[i];}printf("maxlen:%d\n", maxnum); }

結(jié)果：

??3. 編輯距離

定義：字符串a(chǎn)只能通過“替換、插入、刪除”三種操作得到字符串b，期間所做操作的次數(shù)。

例如：abc ——> cb，編輯距離為2。執(zhí)行的操作：a替換為c，刪除字符c.

思路：二維數(shù)組記錄到字符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(chǎn)的第m個(gè)字符是否等于字符串b的第n個(gè)字符，等為0，否則為1.

注意： 空和字串的相似程度時(shí)，距離為別的字串的長度！

圖示：

代碼：

#include <stdio.h> #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\t", c[i][j]);printf("\n");}printf("Lavenshtein distance:%d\n", c[lena][lenb]); return 0; }

執(zhí)行結(jié)果：

同思路問題：

1.最長公共子序列：詳見：http://www.cnblogs.com/kaituorensheng/archive/2013/03/31/2992319

總結(jié)

以上是生活随笔為你收集整理的动态规划整理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。