int size = s.size(); vector<vector<bool>> palindrome(size, vector<bool>(size, true)); for (int i = size - 1; i >= 0; i--) { for (int j = i; j < size; j++) { palindrome[i][j] = s[i] == s[j] && (j - i <= 2 || palindrome[i + 1][j - 1]); } }
string s是输入字符串， palindrome[i][j]表示s.substr(i, j - i + 1)是否为回文。算法时间复杂度和空间复杂度都为O(n^2)。
原文：http://www.cnblogs.com/lakeone/p/5760779.html