#每日一题

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

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

示例 2：
输入：s = "cbbd"
输出："bb"

  • 自己想出来的菜逼解法

public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        // 长度在2以内直接处理返回
        if (s.length() < 2) return s;
        if (s.length() == 2) {
            return chars[0] == chars[1] ? s : String.valueOf(chars[0]);
        }
        // 定义需要返回的最大长度回文字符串
        String max = "";
        // 用来存放字符串中字符的位置
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0 ; i < chars.length; i++) {
            // 回文字符串首尾一定相同
            // 如果前面已经有相同的字符
            if (map.containsKey(chars[i])) {
                int index = map.get(chars[i]);
                int num = i - index;
                // 当max长度已经比当前需要判断的字符串长度长，可直接跳过
                if (!(max.length() < num + 1)) {
                    map.put(chars[i], s.indexOf(chars[i]));
                    continue;
                }
                if (num <= 2) {
                    // 判断最大长度回文字符串
                    max = max.length() > (num + 1) ? max : s.substring(index, i + 1);
                    map.put(chars[i], s.indexOf(chars[i]));
                    continue;
                }
                // 从中间向两边依次进行比较 eg: agccga
                if (num%2 == 1) {
                    boolean flag = true;
                    int left = num/2 + index;
                    int right = num/2 + 1 + index;
                    for (int j = 0; j < (i - right); j++) {
                        // 如果有不相同的说明不是回文字符串
                        if (chars[left - j] != chars[right + j]) {
                            flag = false;
                            // 当前判断的字符串中间是否有和首尾相同的字符
                            int temp = s.indexOf(chars[i], index + 1);
                            if (temp != i) {
                                map.put(chars[i], temp);
                                i--;
                            } else {
                                map.put(chars[i], s.indexOf(chars[i]));
                            }
                            break;
                        };
                    }
                    if (flag) {
                        max = max.length() > (num + 1) ? max : s.substring(index, i + 1);
                        map.put(chars[i], s.indexOf(chars[i]));
                    }
                    continue;
                }
                if (num%2 == 0) {
                    boolean flag = true;
                    int mid = num/2 + index;
                    for (int j = 1; j < (i - mid); j++) {
                        if (chars[mid + j] != chars[mid - j]) {
                            flag = false;
                            int temp = s.indexOf(chars[i], index + 1);
                            if (temp != i) {
                                map.put(chars[i], temp);
                                i--;
                            } else {
                                map.put(chars[i], s.indexOf(chars[i]));
                            }
                            break;
                        };
                    }
                    if (flag) {
                        max = max.length() > (num + 1) ? max : s.substring(index, i + 1);
                        map.put(chars[i], s.indexOf(chars[i]));
                    }
                    continue;
                }
            } else {
                map.put(chars[i], i);
            }
        }
        return max == "" ? String.valueOf(chars[0]) : max;
    }

  • 在我看来有点牛逼的网上找来的动态规划的解法

什么是动态规划文章来源

一、动态规划的三大步骤

动态规划，无非就是利用历史记录，来避免我们的重复。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。

  • 定义数组元素的含义，上面说了，我们会用一个数组来保存历史数组，假设用一维数组dp[]。这个时候有一个非常重要的点，就是规定你这个数组元素的含义，例如你的dp[i]是代表什么意思？

  • 找出数组元素之间的关系式，有点类似归纳法，当我们要计算dp[n] 时，是可以利用 dp[n-1]，dp[n-2]…..dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出元素之间的关系式，例如dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。这也是最难得一步。

  • 找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

    由了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

二、案例详解

简单的一维DP：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

  • 定义数组元素的含义

按我上面的步骤说的，首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有 dp[i] 种跳法。这样，如果我们能够算出 dp[n]，不就是我们要求的答案吗？所以第一步定义完成。

  • 找出数组元素间的关系式

我们的目的是要求 dp[n]，动态规划的题，如你们经常听说的那样，就是把一个规模比较大的问题分成几个规模比较小的问题，然后由小的问题推导出大的问题。也就是说，dp[n] 的规模为 n，比它规模小的是 n-1, n-2, n-3…. 也就是说，dp[n] 一定会和 dp[n-1], dp[n-2]….存在某种关系的。我们要找出他们的关系。

这个怎么找，是最核心最难的一个，我们必须回到问题本身来了，来寻找他们的关系式，dp[n] 究竟会等于什么呢？

对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式

一种是从第 n-1 级跳上来

一种是从第 n-2 级跳上来

由于我们是要算所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]。

  • 找出初始条件

当 n = 1 时，dp[1] = dp[0] + dp[-1]，而我们是数组是不允许下标为负数的，所以对于 dp[1]，我们必须要直接给出它的数值，相当于初始值，显然，dp[1] = 1。一样，dp[0] = 0.（因为 0 个台阶，那肯定是 0 种跳法了）。于是得出初始值：

dp[0] = 0.

int f( int n ){
    if(n <= 1)
    return n;
    // 先创建一个数组来保存历史数据
    int[] dp = new int[n+1];
    // 给出初始值
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    // 通过关系式来计算出 dp[n]
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    // 把最终结果返回
    return dp[n];
}

二维数组的 DP：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？（题目来源）

输入：m = 3, n = 7
输出：28
示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：

输入：m = 7, n = 3
输出：28
示例 4：

输入：m = 3, n = 3
输出：6

提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

机器人左上角走到右下角.png

public int uniquePaths(int m, int n) {
        if (m <= 1 || n <= 1) return 1;
        // 定义二维数组,dp[4][4]的含义就是从左上角走到4，4位置的路径数量
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

最优路径和：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。（题目来源）

说明：每次只能向下或者向右移动一步。

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
 
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public int minPathSum(int[][] grid) {
        int m = grid[0].length;
        int n = grid.length;
        int min = 0;
        int[][] dp = new int[n][m];
        if (m == 1) {
            for (int i = 0; i < n; i++) {
                min += grid[i][0];
            }
            return min;
        }
        if (n == 1) {
            for (int i = 0; i < m; i++) {
                min += grid[0][i];
            }
            return min;
        }
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[0][i] = grid[0][i] + dp[0][i-1];
        }
        for (int i = 1; i < n; i++) {
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j][i] = Math.min(dp[j][i-1], dp[j-1][i]) + grid[j][i];
            }
        }
        return dp[n-1][m-1];
    }

最长回文字符串题解：

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 "ababa''，如果我们已经知道 "bab" 是回文串，那么 "ababa" 一定是回文串，这是因为它的首尾两个字母都是 a。

根据这样的思路，我们就可以用动态规划的方法解决本题。我们用 P(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串（下文表示成 s[i:j] ）是否为回文串：

这里的 其他情况 包含两种可能性

  • s[i,j]本身不是一个回文串

  • i > j, 此时s[i,j] 本身不合法

那么我们可以写出动态规划的状态转移方程：

public String longestPalindrome(String s){
        // 长度小于2直接返回当前字符串
        int l = s.length();
        if (l < 2) return s;
        char[] chars = s.toCharArray();
        // 需要返回的最大长度字符串
        String max = String.valueOf(chars[0]);
        // dp[i][j]标识从i到j位置字符串是否为回文
        boolean[][] dp = new boolean[l][l];
        for (int i = 0; i < l; i++) {
            dp[i][i] = true;
        }
        for (int i = 2; i <= l; i++) {
            for (int j = 0; j < l - 1; j++) {
                int k = i - j - 1;
                if (k >= l) break;
                if (i == 2) dp[j][k] = chars[j] == chars[k];
                dp[j][k] = (dp[j+1][k-1]) && (chars[j] == chars[k]);
            }
        }
        for (int i = 0; i < l - 1; i++) {
            for (int j = 1; j < l; j++) {
                if (dp[i][j] && (j-i+1) > max.length()) max = s.substring(i, j+1);
            }
        }
        return max;
    }