LeetCode-5.最长回文子串-中等

描述：
思路：
x,y为字符串s子串的开始、结束下标, 设f(x, y)表示子序列(x,y)是否是回文字符串
f(x, y) = f(x+1, y-1) && s[x] == s[y]；x等于y时, f(x, y)为true; x等于y+1时, f(x,y)= s[x]==s[x+1]
转移时一定是从短字符串转移到长字符串; 因为(x,y)的组合方式有O(NN)种,每种验证是否为回文需要O(1)
时间复杂度O(NN)

  1.     public String longestPalindrome(String s) {
  2.         if(s.length()==1){
  3.             return s;
  4.         }
  5.         int n = s.length();
  6.         boolean[][] dp = new boolean[n][n];
  7.         int maxLength = 0;
  8.         int maxStart = 0;
  9.         // 对于f(x, y) = f(x+1, y-1) && s[x]==s[y]而言, 长子串的结果依赖与短子串
  10.         // 所以增量在外围, 先计算所有的短子串, 然后计算长子串
  11.         for(int augment=0; augment<n; augment++){
  12.             // end=start+augment<n
  13.             for(int start=0; start+augment<n; start++){
  14.                 int end = start + augment;
  15.                 if(augment==0){
  16.                     dp[start][end] = true;
  17.                 }else if(augment==1){
  18.                     dp[start][end] = s.charAt(start)==s.charAt(end);
  19.                 }else{
  20.                     dp[start][end] = dp[start+1][end-1] && s.charAt(start)== s.charAt(end);
  21.                 }
  22.                 // 全局最长回文子串
  23.                 if(dp[start][end] && (end-start+1)>maxLength){
  24.                     maxLength = end - start+1;
  25.                     // longestStr = s.substring(start, end+1);
  26.                     maxStart = start;
  27.                 }
  28.             }
  29.         }
  30.         return s.substring(maxStart, maxStart+maxLength);
  31.     }

LeetCode-10.正则表达式匹配-困难

LeetCode-32.最长有效括号-困难

LeetCode-42.接雨水-困难

LeetCode-44.通配符匹配 -困难

LeetCode-53.最大子序和-简单

描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

  1.     // 设f(x)为以位置x结尾的最大和连续子数组
  2.     // x=0时,f(x)=nums[0]
  3.     // x>0时,f(x)= f(x-1)>0?(f(x-1)+nums[x]):nums[x]
  4.     // 因为f(x)只与f(x-1)有关,所以设置一个变量即可(滚动数组)
  5.     public int maxSubArray(int[] nums) {
  6.         int pre = nums[0];
  7.         int max = pre;
  8.         for(int i=1;i<nums.length;i++){
  9.             pre = pre<0?nums[i]:(pre+nums[i]);
  10.             max = Math.max(max, pre);
  11.         }   
  12.         return max;
  13.     }

LeetCode-62.不同路径-中等

描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ），机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ），问总共有多少条不同的路径？

  1.     // m,n为行号、列号, 设f(m,n)为可到达右下角的总路径数,反向回溯
  2.     // m>0且n>0时, f(m,n) = f(m-1,n)+f(m,n-1)
  3.     // 考虑边界情况; m=0时, f(m,n)= f(m,n-1); n=0时, f(m,n)=f(m-1,n); m=0且n=0时, f(m,n)=1
  4.     public int uniquePaths(int m, int n) {
  5.         int[][] dp = new int[m+1][n+1];
  6.         for(int i=1;i<=m;i++){
  7.             for(int j=1;j<=n;j++){
  8.                 if(i>1&&j>1){
  9.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
  10.                 }else if(i>1){
  11.                     dp[i][j] = dp[i-1][j];
  12.                 }else if(j>1){
  13.                     dp[i][j] = dp[i][j-1];
  14.                 }else{
  15.                     dp[i][j] = 1;
  16.                 }
  17.             }
  18.         }
  19.         return dp[m][n];
  20.     }

优化：可以优化空间复杂度到O(min(m,n)
f(i, j) 仅与第 i 行和第 i-1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 m≤n，这样空间复杂度降低至 O(min(m,n))

LeetCode-63.不同路径 II-中等

描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ），机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”），现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

  1.     // 设m,n为行号、列号
  2.     // 递推公式类似于leetcode-62
  3.     // m>0且n>0时, dp[m][n] = obstacleGrid[m][n]==0?0:(dp[m-1][n] + dp[m][n-1])
  4.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  5.         int m = obstacleGrid.length;
  6.         int n = obstacleGrid[0].length;
  7.         int[][] dp = new int[m+1][n+1];
  8.         for(int i=0;i<m;i++){
  9.             for(int j=0;j<n;j++){
  10.                 if(obstacleGrid[i][j]==1){
  11.                     dp[i][j] = 0;
  12.                 }else if(i>0 && j>0){
  13.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
  14.                 }else if(i>0){
  15.                     dp[i][j] = dp[i-1][j];
  16.                 }else if(j>0){
  17.                     dp[i][j] = dp[i][j-1];
  18.                 }else{
  19.                     dp[i][j] = 1;
  20.                 }
  21.             }
  22.         }
  23.         return dp[m-1][n-1];
  24.     }

优化空间：同leetcode-63

LeetCode-64.最小路径和-中等 

  1.     // 设m,n为行号、列号, f(m,n)到坐标(m,n)的最小路径和
  2.     // m=0,n=0时, f(m,n)=grid[0][0]
  3.     // m=0,n>0时, f(m,n)=f(m,n-1)+grid[m][n]; m>0,n=0时,f(m,n)=f(m-1, n)+grid[m][n]
  4.     // m>0,n>0时, f(m,n)=Math.min(f(m-1,n), f(m,n-1))+grid[m][n]
  5.     public int minPathSum(int[][] grid) {
  6.         int m = grid.length;
  7.         int n = grid[0].length;
  8.         int[][] dp = new int[m][n];
  9.         for(int i=0;i<m;i++){
  10.             for(int j=0;j<n;j++){
  11.                 if(i==0 && j==0){
  12.                     dp[i][j] = grid[0][0];
  13.                 }else if(i>0 && j>0){
  14.                     dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  15.                 }else if(i>0){
  16.                     dp[i][j] = dp[i-1][j] + grid[i][j];
  17.                 // j>0时    
  18.                 }else{
  19.                     dp[i][j] = dp[i][j-1] + grid[i][j];
  20.                 }
  21.             }
  22.         }
  23.         return dp[m-1][n-1];
  24.     }

LeetCode-70.爬楼梯-简单

描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶，每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
思路：斐波那契数列

  1.     // 设m,n为行号、列号, f(m,n)到坐标(m,n)的最小路径和
  2.     // m=0,n=0时, f(m,n)=grid[0][0]
  3.     // m=0,n>0时, f(m,n)=f(m,n-1)+grid[m][n]; m>0,n=0时,f(m,n)=f(m-1, n)+grid[m][n]
  4.     // m>0,n>0时, f(m,n)=Math.min(f(m-1,n), f(m,n-1))+grid[m][n]
  5.     public int minPathSum(int[][] grid) {
  6.         int m = grid.length;
  7.         int n = grid[0].length;
  8.         int[][] dp = new int[m][n];
  9.         for(int i=0;i<m;i++){
  10.             for(int j=0;j<n;j++){
  11.                 if(i==0 && j==0){
  12.                     dp[i][j] = grid[0][0];
  13.                 }else if(i>0 && j>0){
  14.                     dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  15.                 }else if(i>0){
  16.                     dp[i][j] = dp[i-1][j] + grid[i][j];
  17.                 // j>0时    
  18.                 }else{
  19.                     dp[i][j] = dp[i][j-1] + grid[i][j];
  20.                 }
  21.             }
  22.         }
  23.         return dp[m-1][n-1];
  24.     }

LeetCode-72.编辑距离-困难

LeetCode-85.最大矩形-困难

LeetCode-87.扰乱字符串-困难

LeetCode-91.解码方法-中等

描述：
思路：设x为字符串的某个位置, 设子串s[0:x]的解码总数为f(x)
s[x]=0时, 若s[x-1]=1 or s[x-1]==2则f(x) = f(x-2), 否则f(x)=0
s[x-1]=1时，f(x) = f(x-1) + f(x-2)
s[x-1]=2时，若s[x]<=6，则f(x) = f(x-1) + f(x-2)
其他情况f(x) = f(x-1)

  1.     // 思路：设x为字符串的某个位置, 设子串s[0:x]的解码总数为f(x)
  2.     // s[x]=0时, 若s[x-1]=1 or  s[x-1]==2则f(x) = f(x-2), 否则f(x)=0
  3.     // s[x-1]=1时，f(x) = f(x-1) + f(x-2)
  4.     // s[x-1]=2时，若s[x]<=6，则f(x) = f(x-1) + f(x-2)
  5.     // 其他情况f(x) = f(x-1)
  6.     // 斐波那契数列数列变种, f(x)只和f(x-1)、f(x-2)有关,所以两个变量即可
  7.     public int numDecodings(String s) {
  8.         if(s.charAt(0)=='0'){
  9.             return 0;
  10.         }
  11.         int n = s.length();
  12.         // 初始值,pre表示dp[-1], cur表示dp[0]
  13.         int pre=1, cur = 1;
  14.         for(int i=1;i<n;i++){
  15.             int temp = cur;
  16.             if(s.charAt(i)=='0'){
  17.                 if(s.charAt(i-1)=='1' || s.charAt(i-1)=='2'){
  18.                     cur = pre;
  19.                 }else{
  20.                     return 0;
  21.                 }
  22.             }else if(s.charAt(i-1)=='1' || (s.charAt(i-1)=='2' && s.charAt(i)-'0'<7)){
  23.                 cur = cur + pre;
  24.             }
  25.             pre = temp;
  26.         }
  27.         return cur;
  28.     }

参考：https://leetcode-cn.com/problems/decode-ways/solution/c-wo-ren-wei-hen-jian-dan-zhi-guan-de-jie-fa-by-pr/

LeetCode-96.不同的二叉搜索树 -中等

描述：给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
思路：以i为根节点时，左子树节点范围为[1, i-1], 右子树节点范围是[i+1, n]，分别对左右子树继续构造BST
设5-0 动态规划题目 - 图1 为序列[1..n] 可构成的二叉搜索树数量，5-0 动态规划题目 - 图2为选择以 i 为根节点的二叉搜索树数量
则5-0 动态规划题目 - 图3
选定了 i 为根节点后，左子树只需要构建[1, i-1]，右子树只需要构建[ i+1, n]，左子树的种类就是5-0 动态规划题目 - 图4，右子树的种类就是5-0 动态规划题目 - 图5，虽然右子树的序列不是[1, n-i]，但是[i+1, n]的种类数等同于[1, n-i]，因为都是连续的递增序列
则5-0 动态规划题目 - 图6
参考：

  1.     // 动态规划,事件复杂度O(N*N)
  2.     public int numTrees(int n) {
  3.         int[] g = new int[n+1];
  4.         // 0个节点的二叉搜索树有1种
  5.         g[0] = 1;
  6.         // 1个节点的二叉搜索树有两种
  7.         g[1] = 1;
  8.         // gIndex是序列长度, fIndex是序列的遍历下标
  9.         for(int gIndex=2;gIndex<=n;gIndex++){
  10.             for(int fIndex=1;fIndex<=gIndex;fIndex++){
  11.                 g[gIndex] += g[fIndex-1]*g[gIndex-fIndex];
  12.             }
  13.         }
  14.         return g[n];
  15.     }

LeetCode-97.交错字符串-中等

描述：给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
思路：动态规划

  1.     // 动态规划: f(i,j)表示s1的前i个字符和s2的前j个字符是否能交错构成s3的前i+j个字符
  2.     // f(i,j) = (s1[i-1]==s3[i+j-1]&&f(i-1,j)) || (s2[j-1]==s3[i+j-1]&&f(i,j-1))
  3.     // 时间O(M*N)
  4.     public boolean isInterleave(String s1, String s2, String s3) {
  5.         int m = s1.length(), n = s2.length(), z = s3.length();
  6.         if(m+n!=z){
  7.             return false;
  8.         }
  9.         // dp[i][j]表示s1的前i个字符和s2的前j个字符是否能交错构成s3的前i+j个字符
  10.         boolean[][] dp = new boolean[m+1][n+1];
  11.         for(int i=0;i<=m;i++){
  12.             for(int j=0;j<=n;j++){
  13.                 if(i==0 && j==0){
  14.                     dp[i][j] = true;
  15.                     continue;
  16.                 }
  17.                 char c1 ='1', c2='1', c3=s3.charAt(i+j-1);
  18.                 if(i>0 && j>0){
  19.                     c1 = s1.charAt(i-1);
  20.                     c2 = s2.charAt(j-1);
  21.                     dp[i][j] = (dp[i-1][j] && c1==c3) || (dp[i][j-1] && c2==c3);
  22.                 }else if(i>0){
  23.                     c1 = s1.charAt(i-1);
  24.                     dp[i][j] = dp[i-1][j] && c1==c3;
  25.                 }else{
  26.                     c2 = s2.charAt(j-1);
  27.                     dp[i][j] = dp[i][j-1] && c2==c3;
  28.                 }
  29.             }
  30.         }
  31.         return dp[m][n];
  32.     }

LeetCode-115.不同的子序列-困难

LeetCode-120.三角形最小路径和-中等

描述：给定一个三角形 triangle ，找出自顶向下的最小路径和，每一步只能移动到下一行中相邻的结点上，相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

例子：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）

思路：
设层数有i层, 设g(i)为给定三角形的自顶向下的最小路径和
i为第i层(i>=0),j为第i层的下标(0<=j<=i), f(i,j)为到达坐标(i,j)的最小路径和
则g(i)为区间[0, i]上的f(i,j)的最小值
i=0时, f(i,j) = triangle(i,j)
i>0且j>0时, f(i,j) = Math.min(f(i-1,j), f(i-1,j-1))+triangle(i,j)
i>0且j=0时, f(i,j) = f(i-1,j)+triangle(i,j)
i>0且j=i时, f(i,j) = f(i-1,j-1)+triangle(i,j)

  1.     public int minimumTotal(List<List<Integer>> triangle) {
  2.         int m = triangle.size(), n = triangle.get(m-1).size();
  3.         // 因为, f(i,j)只和f(i-1,j)、f(i-1,j-1)有关, 所以使用滚动数组
  4.         int[] dp = new int[n];
  5.         dp[0] = triangle.get(0).get(0);
  6.         // 通过把j=0和j=i的两种情况从循环区间中拆分出来, 减少分支判断
  7.         for(int i=1;i<m;i++){
  8.             // 处理j=i, 从后向前递减j, 从前往后会导致上一行的f(i-1, j-1)被覆盖
  9.             dp[i] = dp[i-1] + triangle.get(i).get(i);
  10.             for(int j=i-1;j>0;j--){
  11.                 dp[j] = Math.min(dp[j], dp[j-1]) + triangle.get(i).get(j);
  12.             }
  13.             // 处理j=0
  14.             dp[0] += triangle.get(i).get(0);
  15.         }
  16.         int res = dp[0];
  17.         for(int i=0;i<n;i++){
  18.             res = Math.min(res, dp[i]);
  19.         }
  20.         return res;
  21.     }

LeetCode-121.买卖股票的最佳时机-简单

LeetCode-123.买卖股票的最佳时机 III-困难

LeetCode-131.分割回文串-中等

LeetCode-132.分割回文串 II-困难

LeetCode-139.单词拆分-中等

LeetCode-140.单词拆分 II -困难

LeetCode-152.乘积最大子数组 -中等

LeetCode-174.地下城游戏-困难

LeetCode-188.买卖股票的最佳时机 IV-困难

LeetCode-198.打家劫舍 -中等

LeetCode-213.打家劫舍 II-中等

LeetCode-221.最大正方形-中等

LeetCode-264.丑数 II-中等

LeetCode-279.完全平方数-中等

LeetCode-300.最长递增子序列-中等

LeetCode-303.区域和检索 - 数组不可变 -简单

LeetCode-304.二维区域和检索 - 矩阵不可变-中等

LeetCode-309.最佳买卖股票时机含冷冻期-中等

LeetCode-312.戳气球-困难

LeetCode-321.拼接最大数-困难

LeetCode-322.零钱兑换-中等

LeetCode-337.打家劫舍 III-中等

LeetCode-338.比特位计数-中等

LeetCode-343.整数拆分-中等

LeetCode-354.俄罗斯套娃信封问题-困难

LeetCode-357.计算各个位数不同的数字个数 -中等

LeetCode-363.矩形区域不超过 K 的最大数值和-困难

LeetCode-368.最大整除子集-中等

LeetCode-375.猜数字大小 II-中等

LeetCode-376.摆动序列-中等

LeetCode-377.组合总和 Ⅳ-中等

LeetCode-392.判断子序列-简单

LeetCode-403.青蛙过河-困难

LeetCode-410.分割数组的最大值-困难

LeetCode-413.等差数列划分-中等

LeetCode-416.分割等和子集-中等

LeetCode-446.等差数列划分 II - 子序列-困难

LeetCode-464.我能赢吗 -中等

LeetCode-466.统计重复个数-困难

LeetCode-467.环绕字符串中唯一的子字符串-中等

LeetCode-472.连接词 -困难

LeetCode-474.一和零-中等

LeetCode-486.预测赢家-中等

LeetCode-494.目标和-中等

LeetCode-514.自由之路-困难

LeetCode-516.最长回文子序列-中等

LeetCode-517.超级洗衣机 -困难

LeetCode-523.连续的子数组和-中等

LeetCode-546.移除盒子-困难

LeetCode-552.学生出勤记录 II -困难

LeetCode-576.出界的路径数-中等

LeetCode-600.不含连续1的非负整数-困难

LeetCode-629.K个逆序对数组-困难

LeetCode-638.大礼包-中等

LeetCode-639.解码方法 II-困难

LeetCode-646.最长数对链-中等

LeetCode-647.回文子串-中等

LeetCode-650.只有两个键的键盘 -中等

LeetCode-664.奇怪的打印机-困难

LeetCode-673.最长递增子序列的个数-中等

LeetCode-688.“马”在棋盘上的概率-中等

LeetCode-689.三个无重叠子数组的最大和-困难

LeetCode-691.贴纸拼词-困难

LeetCode-698.划分为k个相等的子集-中等

LeetCode-712.两个字符串的最小ASCII删除和-中等

LeetCode-714.买卖股票的最佳时机含手续费-中等

LeetCode-718.最长重复子数组-中等

LeetCode-730.统计不同回文子序列-困难

LeetCode-740.删除与获得点数-中等

LeetCode-741.摘樱桃-困难

LeetCode-746.使用最小花费爬楼梯-简单

LeetCode-764.最大加号标志-中等

LeetCode-787.K 站中转内最便宜的航班 -中等

LeetCode-790.多米诺和托米诺平铺-中等

LeetCode-799.香槟塔-中等

LeetCode-801.使序列递增的最小交换次数-中等

LeetCode-808.分汤-中等

LeetCode-813.最大平均值和的分组 -中等

LeetCode-818.赛车-困难

LeetCode-837.新21点 -中等

LeetCode-838.推多米诺-中等

LeetCode-847.访问所有节点的最短路径-困难

LeetCode-871.最低加油次数 -困难

LeetCode-873.最长的斐波那契子序列的长度-中等

LeetCode-877.石子游戏-中等

LeetCode-879.盈利计划-困难

LeetCode-887.鸡蛋掉落-困难

LeetCode-898.子数组按位或操作-中等

LeetCode-902.最大为 N 的数字组合-困难

LeetCode-903.DI 序列的有效排列-困难

LeetCode-920.播放列表的数量-困难

LeetCode-931.下降路径最小和 -中等

LeetCode-935.骑士拨号器-中等

LeetCode-940.不同的子序列 II-困难

LeetCode-943.最短超级串 -困难

LeetCode-956.最高的广告牌-困难

LeetCode-960.删列造序 III-困难

LeetCode-964.表示数字的最少运算符-困难

LeetCode-968.监控二叉树 -困难

LeetCode-975.奇偶跳-困难

LeetCode-978.最长湍流子数组 -中等

LeetCode-982.按位与为零的三元组-困难

LeetCode-983.最低票价 -中等

LeetCode-1000.合并石头的最低成本-困难

LeetCode-1012.至少有 1 位重复的数字-困难

LeetCode-1024.视频拼接 -中等

LeetCode-1025.除数博弈-简单

LeetCode-1027.最长等差数列-中等

LeetCode-1039.多边形三角剖分的最低得分-中等

LeetCode-1043.分隔数组以得到最大和-中等

LeetCode-1048.最长字符串链-中等

LeetCode-1049.最后一块石头的重量 II-中等

二.滚动数组题目

LeetCode-97.交错字符串-中等
63. 不同路径 II
70. 爬楼梯
剑指 Offer 46. 把数字翻译成字符串
120. 三角形最小路径和

三.股票问题

参考：
大厂动态规划面试汇总，提升内功