回文序列问题

Example 1:

Input: 121

Output: true

Example 2:

Input: -121

Output: false

Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

示例 1：

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

时间复杂度： O(n^2) 两个for循环

空间复杂度： O(n^2) dp数组的大小

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"

输出：[["a","a","b"],["aa","b"]]

思路：动态规划得到每个子串是否为回文子串，然后从头开始回溯算法

时间复杂度：O(N * 2^N)

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"

输出：1

解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

思路：

时间复杂度=空间复杂度=O(n^2)

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"

输出：3

解释：三个回文子串: "a", "b", "c"

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"

输出：4

解释：一个可能的最长回文子序列为 "bbbb" 。

给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。

通过从 S 中删除 0 个或多个字符来获得子序列。

如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。

如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。

示例 1：

输入：

S = 'bccb'

输出：6

解释：

6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。

注意：'bcb' 虽然出现两次但仅计数一次。

回文指从左往右和从由往左读到相同内容的文字。比如: aba，abba，level。

回文具有对称性。

回文算法的目标是把最长的回文从任意长度的文本当中寻找出来。比如：从123levelabc中寻找出level。

参考资料

通过定义一个s字符数组，gets函数控制输入

i、j双指针来回判断字符数组的位置，和对应位置的值的比较，

while循环的条件 i<=j&&s[i]==s[j]

最终判断i、j的关系，如果i<=j说明存在对应位置不等的情况就是不是回文串

参考资料

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

注意看实现思路

参考

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

输入: "cbbd"

输出: "bb"

解题思路：

参考

解题思路：

1.双重for循环+判别回文串

2.单纯for循环+中心扩散法

3.动态规划

参考

大神Leetcode

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解 决策过程最优化 的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如 线性规划、非线性规划 )，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定， 它依赖于当前面临的状态，又影响以后的发展 。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个 前后关联具有链状结构的多阶段过程 就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的， 决策依赖于当前状态，又随即引起状态的转移 ，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。 动态规划算法与分治法类似 ，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是， 适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的 。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

以一个例子来说明动态规划的概念(leetcode第5题最长回文子串)：

在这个例子中，一个字符串如果是回文子串，那么去掉头尾也照样是回文子串。而每一个字符都有可能是最长回文子串的一部分。

上面这个例子使用一个二维数组表示各个阶段的状态，这个二维数组的行是子串的起始位置，列是子串的结束位置。由于j>=i，所以只需要考虑二维数组的主对角线的上半部分，对角线上的值永远是true。用true表示这个子串是回文串，false不是回文串。那么对于某个固定位置的数组元素来说，它的值依赖于左下角的元素的值。进行填充的时候只能一列一列地进行填充，同一列的元素从上到下依次填充。

---