利用动态规划求解回文子串_如何用动态规划解决回文字串

本文为我刷leetcode上题目所用方法

  class Solution {

  public:
  int countSubstrings(string s) {
  int len = s.size();
  int count = len;
  if (len == 0) return 0;
  vector<vector<bool>>flag(len, vector<bool>(len, false));
  for (int i = 0; i < len; i++)
  flag[i][i] = true;
  for (int i = 1; i < len; i++)
  {
  if (s[i] == s[i - 1])
  {
  flag[i - 1][i] = true;
  count++;
  }
  
  }
  for (int step = 2; step < len; step++)
  {
  for (int i = 0; i < len - step; i++)
  {
  if (s[i] == s[i + step] && flag[i + 1][i + step - 1])
  {
  flag[i][i + step] = true;
  count++;
  }
  }
  }
  return count;
  }
  };