动态规划题目收集

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

暴力解法

暴力解法也没啥好说就是逐个比对

例如比对 BABAD 子串

可以输出 BAB 也可以输出 ABA

class Solution {
    public String longestPalindrome(String s) {
        if (null == s) {
            return "";
        }
        int len = s.length();
        int max = 0; // 注意，需要一个 Max 来找到最大的回文子串
        String ans = "";

        for (int i = 0; i < len; i++) {
            // 别忘了加上 = 号
            for (int j = (i + 1); j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromicString(test) && test.length() > max) {
                    ans = test;
                    max = Math.max(max, ans.length());
                }
            }
        }
        return ans;
    }

    // 判断是否是回文串（这里使用双指针的方法）
    boolean isPalindromicString(String s) {
        int left = 0;
        int right = s.length() - 1;
        // 使用双指针的方式判断
        while( left < right ) {
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }

        return true;
    }
}

二维数组的动态规划

这个方法转载自 最长回文子串问题（五种方法）

回文串两边加上两个相同字符，会形成一个新的回文串。

方法是，建立二维数组 dp ，找出所有的回文子串。

dp[i][j] 记录子串 i..j 是否为回文串。

首先，单个字符就形成一个回文串，所以，所有 dp[i][i] = true。

然后，容易得到递推关系：

如果字符 s[i] 和 s[j] 相等，并且子串 i+1..j-1 是回文串的话，子串 i..j 也是回文串。即，如果 s[i] == s[j] 且 dp[i+1][j-1] = true 时，dp[i][j] = true。

这是本方法中主要的递推关系。

不过仍要注意边界情况，即 子串 i+1..j-1 的有效性 ，当 i+1 <= j-1 时，它才有效。

反之，如果不满足，此时 j <= i+1 ，也就是子串 i..j 最多有两个字符，如果这两个字符 s[i] 和 s[j] 相等，那么也是回文串。

至此，递推关系已经分析完。

最后，考虑到 主要的递推关系 是由已知子串 i+1..j-1 的情况， 递推到 i..j 的情况， 因此，迭代过程需要反序迭代变量 i ，正序迭代 j。

此外，可以通过一个表格，来理解整个 dp 数组的规划过程。

上面的表格填表过程：

1. 初始化所有方格写 false。
2. 填写对角线写 true。
3. 自对角线右下角开始，自下而上、自左而右，按箭头方向根据递推关系填表。

最后，找到所有回文子串后，即可找到最长回文子串和其长度。

连续子数组的最大和（简单）

描述： 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 $O(n)$.

示例1

输入：[1,-2,3,10,-4,7,2,-5]

返回值：18

说明：输入的数组为{1,-2,3,10,-4,7,2,-5}，
和最大的子数组为{3,10,-4,7,2}，因此输出为该子数组的和 18。

题解，简单的动态规划

import java.lang.Math;

public class Solution {
    public  int FindGreatestSumOfSubArray(int[] array) {
            int res = array[0]; //记录当前所有子数组的和的最大值
            int max=array[0];   //包含array[i]的连续数组最大值
            for (int i = 1; i < array.length; i++) {
// 核心问题，为什么这里 max(array[i] + dp[i-1], array[i]), 是和 array[i] 做比较？
// 因为题目要求连续子向量（设为X）的和的最大值，
// 如果dp[i-1]+array[i]<array[i]，
// 那么之前计算dp[i-1]的子向量肯定不是所求X的开头段，
// 因为array[i]已经更大了，它才有可能是X的开头段。
                max = Math.max(max + array[i], array[i]);
                res = Math.max(max, res);
            }
            return res;
    }
}