本文主要是介绍POJ 1159 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题还是看了discuss才知道居然是求与反串(reverse)的最长公共子序列（LCS）的。最小的需要insert的数目k = N - LCS(str, reverse).其中N是原字符串的长度，reverse是原字符串的reverse。
问题是二维的空间复杂度超过了要求，所以这里用的是覆盖的方法。因为LCS[i][j] = 1+LCS[i - 1][j - 1](if str1[i] == str2[j])或者LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])。都只需要前一行的结果。所以开一个一维的数组就够了。
DP的想法似乎也能想得通。前后两个指针i,j。如果str[i]==str[j]，那么dp[i][j] = dp[i + 1][j - 1];负责，有两种可能，1是在前面（即左边）加一个str[j]，2是在后面加一个str[i],两者取小的那个，所以dp[i][j] = 1 + min(dp[i][j - 1], dp[i + 1][j]).没看解法，估计是这样的。
| Accepted | 264K | 1860MS | C++ | 1399B |
/*
ID: thestor1
LANG: C++
TASK: poj1159
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;int LCS(string &str1, string &str2)
{int N = str1.size();assert (str2.size() == N);// std::vector<std::vector<int> > lcs(N, std::vector<int>(N, 0));std::vector<int> lcs(N, 0);int prev = 0, next;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){next = lcs[j];if (str1[i] == str2[j]){if (i == 0 || j == 0){lcs[j] = 1;}else{lcs[j] = 1 + prev;}}else{if (i == 0 && j == 0){lcs[j] = 0;}else if (i == 0){lcs[j] = lcs[j - 1];}// else if (j == 0)// {// lcs[j] = lcs[i - 1][j]; // }else if (j != 0){lcs[j] = max(lcs[j - 1], lcs[j]); }}prev = next;}}return lcs[N - 1];
}int main()
{int N;cin >> N;string str;cin >> str;assert (str.size() == N);string reverse;for (int i = N - 1; i >= 0; --i){reverse.push_back(str[i]);}cout << N - LCS(str, reverse) << endl;return 0;
}这篇关于POJ 1159 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
