# Exercise - Minimum Deletions in a String to make it a Palindrome

這題挺不錯的，算是這系列的活用題：

解法一 - DP

using namespace std;

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

class MDSP {

public:
  int findMinimumDeletions(const string &st) {
    // subtracting the length of Longest Palindromic Subsequence from the length of
    // the input string to get minimum number of deletions
    return st.length() - findLPSLength(st);
  }

  int findLPSLength(const string &st) {
    // dp[i][j] stores the length of LPS from index 'i' to index 'j'
    vector<vector<int>> dp(st.length(), vector<int>(st.length()));

    // every sequence with one element is a palindrome of length 1
    for (int i = 0; i < st.length(); i++) {
      dp[i][i] = 1;
    }

    for (int startIndex = st.length() - 1; startIndex >= 0; startIndex--) {
      for (int endIndex = startIndex + 1; endIndex < st.length(); endIndex++) {
        // case 1: elements at the beginning and the end are the same
        if (st[startIndex] == st[endIndex]) {
          dp[startIndex][endIndex] = 2 + dp[startIndex + 1][endIndex - 1];
        } else { // case 2: skip one element either from the beginning or the end
          dp[startIndex][endIndex] =
              max(dp[startIndex + 1][endIndex], dp[startIndex][endIndex - 1]);
        }
      }
    }
    return dp[0][st.length() - 1];
  }
};

int main(int argc, char *argv[]) {
  MDSP *mdsp = new MDSP();
  cout << mdsp->findMinimumDeletions("abdbca") << endl;
  cout << mdsp->findMinimumDeletions("cddpd") << endl;
  cout << mdsp->findMinimumDeletions("pqr") << endl;

  delete mdsp;
}