51工具盒子#每日一题 {#heading-1}
给你一个字符串 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;
}
- 在我看来有点牛逼的网上找来的动态规划的解法
什么是动态规划++文章来源++ {#heading-2}
一、动态规划的三大步骤 {#heading-3}
动态规划，无非就是利用历史记录 ，来避免我们的重复。而这些历史记录，我们得需要一些变量 来保存，一般是用一维数组 或者二维数组来保存。
-
定义数组元素的含义，上面说了，我们会用一个数组来保存历史数组，假设用一维数组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] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。
二、案例详解 {#heading-4}
++简单的一维DP++：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 {#heading-5}
- 定义数组元素的含义
按我上面的步骤说的，首先我们来定义 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" ）。 {#heading-6}
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为"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
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 ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。（题目来源） {#heading-7}
**说明：**每次只能向下或者向右移动一步。
示例 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;
}
