最長公共子序列——動态規劃

動态規劃步驟：

1、根據下面公式求出最大子序列的長度

C[i,j]為一個二維數組，用來儲存子序列的長度

假設這兩個序列分别是：X={A,B,C,B,D,A,B}    Y={B,D,C,A,B,A}

長度分别為        m            和   n

得出最長子序列的長度為4

2、根據回溯法求出最長子序列

i和j分别從m，n開始，遞減循環直到i = 0，j = 0。其中，m和n分别為兩個串的長度。

  ·如果str1[i] == str2[j]，則将str[i]字元插入到子序列内，i--，j--；

  ·如果str1[i] != str[j]，則比較L[i,j-1]與L[i-1,j]，L[i,j-1]大，則j--，否則i--；（如果相等，則任選一個）

接着我們來看一道題

題目描述：

給定一個字元串s，你可以從中删除一些字元，使得剩下的串是一個回文串。如何删除才能使得回文串最長呢？輸出需要删除的字元個數

輸入描述:

輸入資料有多組，每組包含一個字元串s，且保證:1<=s.length<=1000.

輸出描述:

對于每組資料，輸出一個整數，代表最少需要删除的字元個數。

輸入例子:

abcda 

google

輸出例子:

2 

2

實作思想：

先儲存字元串到str1

再儲存字元串逆序後的結果到str2

#include <iostream>
#include <string>
#include <stack>
using namespace std;

void Reverse(char* first,char* second)
{
	char tmp;
	while (first < second){
		tmp = *first;
		*first = *second;
		*second = tmp;
		++first;
		--second;
	}
}

int main()
{
	char s[1000];
	while (cin >> s){
		string str1(s);
		/*string str2(s);
		reverse(str2.begin(), str2.end());*/

		Reverse(s,(s+str1.size()-1));
		string str2(s);

		//在str1、str2中找出最大公共子序列（LCS）
		int m = str1.size();
		int n = str2.size();
		int* C = new int[ (m+1) * (n+1) ];//用來儲存各子序列的長度
		char* s1 = (char*)str1.c_str();
		char* s2 = (char*)str2.c_str();
		//填充二維數組C
		for (int i = 0; i <= m; ++i){
			for (int j = 0; j <= n; ++j){
				if (i == 0 || j == 0){
					C[i*(n+1) + j] = 0;
				}
				else{
					if (*(s1 + i-1) == *(s2 + j-1)){
						C [i*(n+1) + j] = C[(i-1)*(n+1) + j-1]+1;
					}
					else{
						C[i*(n+1) + j] = (C[(i - 1)*(n+1) + j] > C[i*(n+1) + j - 1] ? C[(i - 1)*(n+1) + j] : C[i*(n+1) + j - 1]);
					}
				}
				cout << C[i*(n + 1) + j] << " ";
			}
			cout << endl;
		}
		stack<char> stmp;
		for (int i = m,j = n; i >= 0&&j>=0;){
			if (*(s1 + i-1) == *(s2 + j-1)){
				stmp.push(*(s1+i-1));
		
				--i;
				--j;
			}
			else{
				*(C + i*(n + 1) + j - 1) > *(C + (i - 1)*(n + 1) + j )? --j : --i;
			}
		}
		int size = str1.size() - stmp.size();

		cout << size<<endl;
	}
	return 0;
}