动态规划问题--最长公共子序列（LCS）问题--删除一些字符使得剩下的是一个回文子串

题目：给定一个字符串s，你可以删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长，输出需要删除的字符个数。

输入描述：输入数据包含多组，每组包含一个字符串s，并且保证：1<= s.length<=1000。

输出描述：对于每一组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子：google

输出例子：2

知识点：

最长公共字串和公共子序列的区别，字串必须连续，子序列不必连续。

vector<vector<int> > dp(m + 1, vector<int > (n + 1, 0);//二维数组的写法

字符串下标是从0开始，但是二位数组的计算是从1开始。

算法思想：

首先复制字符串，并将新的字符串反转。先求出两个字符串的的公共子序列，用整个字符串长度减去公共子序列的长度。

那么如何求公共子序列呢，这里用到了动态规划的思想，确定状态并且找到状态转移方程。

状态：两个字符串分别为str1，str2，下标分别为m，n，最长公共子序列的长度为dp；

转移方程：如果str1[m] == str2[n]，则dp[i][j] = dp[i - 1][j - 1] + 1;

 如果str1[m] != str2[n]，则dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

如图：

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>


using namespace std;


int main(){
    string str1;
    while(cin>>str1){
        string str2 ="";
        str2 += str1;
        reverse(str2.begin(), str2.end());
        int m = str1.size();
        int n = str2.size();
        vector<vector<int> > dp(m + 1, vector<int > (n + 1, 0));
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(str1[i - 1] == str2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        
        cout<<m - dp[m][n]<<endl; 
    }
    return 0;
}