暴力递归就是尝试
1：把问题转化为规模缩小了的同类问题的子问题
2：有明确的不需要继续进行递归的条件(base case)
3：有当得到子问题的结果之后的决策过程
4：返回每一个子问题的解给上级调用者
暴力递归–>动态规划
动态规划就是暴力尝试减少重复计算的技巧而已， 这种技巧就是一个大型套路，先写出用尝试的思路解决问题的递归函数，而不用操心时间复杂度 这个过程是无可替代的，没有套路的，只能依靠个人智慧，或者足够多的经验
但是怎么把尝试的版本，优化成动态规划，是有固定套路的，大体步骤如下
1)找到什么可变参数可以代表一个递归状态，也就是哪些参数一旦确定，返回值就确定了
2)把可变参数的所有组合映射成一张表，有 1 个可变参数就是一维表，2 个可变参数就 是二维表，…
3)最终答案要的是表中的哪个位置，在表中标出
4)根据递归过程的 base case，把这张表的最简单、不需要依赖其他位置的那些位置填好值
5)根据递归过程非base case的部分，也就是分析表中的普遍位置需要怎么计算得到，那 么这张表的填写顺序也就确定了
6)填好表，返回最终答案在表中位置的值
1.暴力递归
1.汉诺塔
public static void hannuo(int n){
if (n>0){
func(n,"左","右","中");
}
}
//1-i的圆盘（i越大，圆盘越大） 目标时from ->to other是另外一个柱子 !!每个子问题都保证自己的底满足规则即可
public static void func(int i,String start,String end,String other){
if (i == 1){//base case 只剩下最小的盘 直接放就可以
System.out.println("移动 1 号盘，从"+start+"到"+end);
}else {
//先把i-1（大盘子i的上一个）放到辅助柱子上
func(i-1,start,other,end);
//第i-1的先搁置一边，这时候代表压在(i-1)下的大盘子i可以正确的放到目标柱子
System.out.println("移动"+i+" 号盘，从"+start+"到"+end);
//再把i-1从辅助柱子移到目标柱子。这时候满足规则，只能小压大
func(i - 1, other, end, start);
}
}
2.字符串的全部子序列
描述：比如给定abc 打印 abc ab,ac,a,bc ,b,c,null
思路：每个字符都选择要还是不要，和二叉树类似，再接着，每个子树又要选择要还是不要。就像下面这种，
开始选择要a或者不要a两种情况，然后根据前面的结果继续要b不要b两种情况，最终2^n种
public static void printAllSubsquence(String str){
char[] chs = str.toCharArray();
process(chs, 0,new ArrayList<Character>());
}
//来到i的位置，要还是不要两条路 ,res储存的是之前的选择所形成的的列表
private static void process(char[] chs, int i, List<Character> res) {
//base case 只要来到了终止的位置，即遍历完所有的字符串的时候，打印出来结果即可
if (i ==chs.length){
printList(res);//自己的处理逻辑 我这里是打印 也可以自己收集起来然后遍历所有结果打印
return;
}
//把之前的结果拷贝一份，让我们的下一个栈操作这个拷贝的就行，原来的后面还要用，所以需要拷贝。
List<Character> resKeep = copyList(res);
resKeep.add(chs[i]); //加入当前字符
//继续走要当前字符的路 比如为空 加入后变为'a'，那我们就要'a'的路
process(chs,i+1,resKeep);
//拷贝一份，因为我们没有添加当前字符，而是直接走的i+1下一个字符的这条路
List<Character> resNoinclude = copyList(res);
process(chs,i+1,resNoinclude);//不要当前的路
}
//工具函数，将之前存放的结果的list再复制一份放到一个新的list里
private static List<Character> copyList(List<Character> oldList) {
if (oldList == null){
return new ArrayList<Character>();
}
ArrayList<Character> newList = new ArrayList<>();
for (Character ch : oldList) {
newList.add(ch);
}
return newList;
}
//工具函数，打印list里所有的字符串
private static void printList(List<Character> res) {
for (Character ch : res) {
System.out.print(ch);
}
System.out.println();
}
3.字符串全排列且去重
描述：如输入字符串abc，则字符a、b、c 所能排列出来的所有字符串：abc、acb、bac、bca、cab 和 cba
思想：就是去试，str[0…i-1]范围上，是之前做的选择，是已经试好的（可以看做固定的），str[i…]范围上，所有的字符都可以在i位置上，后续都去尝试
public static ArrayList<String> CharQuanpailie(String str) {
if (str == null || str.length() == 0) return res;
ArrayList<String> res = new ArrayList<>();
char[] chs = str.toCharArray();
process(chs, 0, res); //从i=0开始
return res;
}
//把所有字符串形成的全排列加到res后返回
public static void process(char[] str, int i, ArrayList<String> res) {
//base case i作为指针走到末尾加入结果
if (i == str.length){
//这个str是被复用的，是递归栈保证了它每次先入栈，在方法调用的时候再从栈里取出而不销毁
res.add(String.valueOf(str));
//所以i == str.length时其实是最后一个str被加到res里
}
//为了不重复，分支限界，设置标志位，比如字符串中有两个a，则后面再次遇到a就不用再来一遍了
boolean[] visit = new boolean[26];
//从i位置开始，其余的所有字符都要试一遍组合，直到字符用完
for (int j = i; j < str.length; j++) {
//26个字母，减去'a'后变为 a对应0位置，b对应1位置....,哪个位置被用了，这个位置就置true
//如果该字符没被用，就可以通过该字符来全排列，这样就保证了不重复的字母才被考虑
if (!visit[str[j]-'a']){
//如果之前没用，现在用了，该位置置true
visit[str[j] - 'a'] = true;
//i往后所有的字符都可以来到i位置，比如开始'abc'则a后面的b、c字符也可以来到当前a位置
swap(str, i, j);
process(str,i+1,res);//j来到位置i后,从i+1开始尝试
//尝试完再放回去，把交换完的复原，依次往复
swap(str, i, j);
}
}
}
//工具类，交换位置
private static void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
4.逆序实现栈
描述：给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现?
思路：
getAndRemoveLastElement方法递归之后：每次把当前值压回去
public class reverseStack {
public static void reverseStack(Stack<Integer>stack){
if (stack.isEmpty()) return;
int i = getAndRemoveLastElement(stack);
//弹出一个数之后，现在栈只有1，2了 然后继续逆序找到最后一个数字
reverseStack(stack);
stack.push(i);
}
//移除栈底元素并返回,剩下的盖下来
public static int getAndRemoveLastElement(Stack<Integer> stack){
Integer result = stack.pop();
//如果弹出一个数栈为空了，说明这个数就是最后一个了，直接返回
if (stack.isEmpty()) return result;
else {
int last = getAndRemoveLastElement(stack);//获得返回的
stack.push(result);//然后将当前的值重新入栈
return last;//返回上个栈返回的元素
}
}
}
5.取扑克
public static int win(int[] arr) {
if (arr == null || arr.length == 0) return 0;
//玩家1在【0，n-1】范围上先手， 玩家2在【0，n-1】范围上后手
//谁得分大谁赢
return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
}
//先手 在【i.j】范围上返回经过先手能得到的最大分数
public static int first(int[] arr,int i,int j){
if (i==j) return arr[i]; //先手，剩一张牌，就只能拿这张牌了
//由于只能取两边，取i后，剩下的为【i+1,j】范围，第二次取数（第二次可以看做后手）；或者取j后，剩下的为【i,j-1】范围，第二次取数
//如何对先手的人有利，那就是取最大
return Math.max(arr[i]+second(arr,i+1,j),arr[j]+second(arr,i,j-1));
}
//后手 返回经过后手后，在【i.j】范围上能得到的最大分数
private static int second(int[] arr, int i, int j) {
if (i==j) //base case 后手，只有一个数，那会被先手拿走，所以只能得到0
return 0;
//如果别人先拿走i，我只能在【i+1,j】范围上轮到我先手
// 如果别人先拿走j，我只能在【i,j-1】范围上轮到我先手
//如何对后手的人有利，这里逆向思维，后手只有通过先手的结果确定，所以是动态的，两人敌对又聪明，分数越高越好。那么，作为后手的最大分数是被人决定的（先手的那个人），别人只会把最差情况给我，所以我要把最差情况最小化
return Math.min(first(arr, i + 1, j), first(arr, i, j - 1));
}
6.岛屿问题
思想：当当前位置为1的时候，就开始递归感染他附近的位置，并置为2，然后递归的时候就会计算有多少岛屿
public int numIslands(char[][] grid) {
//如果数组为null 或者第一行为null
if(grid == null || grid[0]==null) return 0;
int row=grid.length;
int res=0;
for(int i=0;i<grid.length;i++)
for(int j=0;j<grid[0].length;j++){
//如果当前位置为 1 则代表有岛
if(grid[i][j]=='1'){
res++;
//数量增加之后，把它相邻的1全部感染了
infect(grid,i,j,grid.length,grid[0].length);
}
}
return res;
}
//感染逻辑
public void infect(char[][] grid,int i,int j,int line,int row){
//当行大于了最大行数，或者行小于0，或者列同样如此，或者当前数不为1，直接跳出返回
if(i>=line || i<0 || j>=row || j<0 || grid[i][j]!='1') return ;//终止条件
//否则 说明当前位置为1，就需要把当前位置感染为不为1的其他数，这里我设置的为2，反正不为1就行了
grid[i][j]='2';
//然后递归的感染前后左右
infect(grid,i+1,j,line,row);//前 俯视图
infect(grid,i-1,j,line,row);//后
infect(grid,i,j+1,line,row);//右
infect(grid,i,j-1,line,row);//左
}
2.解码方法
1.数字转字符串
数字转字符串力扣地址：跟19题类似 约束版 爬楼梯 只是这道题由于0可以对应a 则 方案一始终都是可行的
public static int translateNum(int num) {
String str = String.valueOf(num);
int[] dp=new int[str.length()+1];
dp[0]=1;
for (int i = 1; i <= str.length(); i++) {
dp[i]=dp[i-1];
//当前字符不是字符串第一个字符 && (前一个字符为1 || 前一个字符为2&&当前字符小于7) 则可以从i-2的位置到达到当前位置 可以理解为i和i-1看成一个整体cur i-2就可以来到当前整体
if(i>1 && (str.charAt(i-2)=='1' || (str.charAt(i-2)=='2'&&str.charAt(i-1)<='5')))
dp[i]+=dp[i-2];
}
return dp[str.length()];
}
2.解码方法
/*相当于约束版本的爬楼梯 dp[i]=dp[i-1]+dp[i-2] dp[i]代表来到当前情况有多少种
来到当前字符cur 有2中情况：
1：只由当前字符解码 需要判断当前字符是不是0 dp[i-1]
2：由当前字符和前一个字符相加来解码 需要判断是否超过了26 dp[i-2]
然后方案一的情况+方案二的情况就是当前的cur的情况
*/
public int numDecodings(String s) {
if(s.charAt(0)=='0') return 0;
int[] dp=new int[s.length()+1];
dp[0]=1;//当有0个数则为空串 则有1种
for (int i = 1; i <=s.length() ; i++) {
// 由于我是从1开始算的 所以s.charAt(i-1)表示当前字符
//如果当前字符为0，则方案一的情况为0
if(s.charAt(i-1)=='0') dp[i]=0;
//否则就是dp[i]=dp[i-1]
else dp[i]=dp[i-1];
//当前字符不是首字母 && (前一个字符为1 || 前一个字符为2&&当前字符小于7) 则可以从i-2的位置到达到当前位置 相当于走2步嘛
if(i>1 && (s.charAt(i-2)=='1' || (s.charAt(i-2)=='2'&&s.charAt(i-1)<'7')))
dp[i]+=dp[i-2];
}
return dp[s.length()];
}
3.背包问题
/*dp[i][j]表示：对于前i个物品，当前背包的容量为j时，这种情况下可以装下的最大价值是dp[i][j]。分两种情况
1.没有把这第i个物品装入背包，那么最大价值dp[i][j]=dp[i-1][j]。你不装嘛，那就继承之前的结果。
2.把这第i个物品装入了背包，那么dp[i][j]=dp[i-1][v-vw[i][0]]+vw[i][1]。
但还是需要和不装入进行大小比较，取价值最大的。
*/
public int knapsack (int V, int n, int[][] vw) {
//dp[i][j]代表来到当前位置j和使用了vw[0..i]的最大最大重量
int[][] dp=new int[n][V+1];
//当背包V=0 则初始化第0列全为0
for(int i=0;i<n;i++)
dp[i][0]=0;
//初始化第0行 这里我没有像上图多定义了一行（0个物品） 下面我直接从第一个物品开始的
for(int i=0;i<V+1;i++)
dp[0][i]=i>=vw[0][0]?vw[0][1]:0;
for(int i=1;i<n;i++){
for(int v=1;v<V+1;v++){
/*当前位置可以选择装还是不装
1.当前位置不装 则当前位置直接是他上面那个状态 dp[i][v]=dp[i-1][v];
2.当前位置装 则v-vw[i][0]代表需要装当前位置的时候 前面最大只能有v-vw[i][0]的体积,则 取dp[i-1][v-vw[i][0]]的位置为前面最大能够装的体积的重量最大值,然后加上当前位置的重量 最后然后1和2取最大值;
如果前面的v-vw[i][0]体积>=0，说明要了当前位置 前面的位置也能到达，则取方案1和2中的较大值。如果v-vw[i][0]体积<0，则说明要了当前位置之后，前面的又不满足了，这个时候当前位置只能选择方案1*/
if(v-vw[i][0]>=0)
dp[i][v]=Math.max(dp[i-1][v],dp[i-1][v-vw[i][0]]+vw[i][1]);
else dp[i][v]=dp[i-1][v];
}
}
return dp[n-1][V];
}
背包问题2：背包容量为w。一共有n袋零食, 第i袋零食体积为v[i]。在总体积不超过背包容量的情况下，一共有多少种零食放法(总体积为0也算一种放法)
public static int ways(int[] arr, int w) {
if (arr == null || arr.length == 0 || w < 0) return 0;
//dp[i][j]代表当前位置使用了arr[0..i]个物体（不一定每个数都要）放到j体积的方法数
int[][] dp = new int[arr.length][w + 1];
//初始化第0列，因为体积为0也算一种 所以当总体积j=0 也算一种
for (int i = 0; i < arr.length; i++)
dp[i][0] = 1;
//初始化第0行 看看当前j是否大于v[0] 如果大于等于则放得下 否则放不下
for (int j = 1; j <= w; j++)
dp[0][j] = j >= arr[0] ? 2 : 1;
/*来到当前位置dp[i][j]有2种情况
1.不要当前位置的i 直接是当前位置上面那个i-1位置得来 dp[i][j] = dp[i - 1][j];
2.要当前位置i 则到上面那个i-1位置需要的容量最大就是j-arr[i] 当然前提条件就是能够到达j-arr[i]体积大小
也就是j-arr[i]>=0 则dp[i][j] = dp[i - 1][j - arr[i]];
然后1+2就是当前位置的总方法数 */
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= w; j++) {
dp[i][j] = dp[i - 1][j];
if (j - arr[i] >= 0) {
dp[i][j] += dp[i - 1][j - arr[i]];
}
}
}
return dp[arr.length - 1][w];
}
4.停在原地的方法数
public int numWays(int steps, int arrLen) {
if(arrLen==1) return 1;
//如果不这么写的话 会超出内存 当步数不大但是数组长度很长时，数组靠后大部分位置没有必要去遍历
//因为步长为steps，而你要到达0 所以是一个来回 理论上指针可以到达的极限位置也就是steps/2+1，因此可以修改取值范围、
int maxCol = Math.min(steps/2+1,arrLen-1);
//dp[i][j]代表 使用了i步之后 来到j位置 的方法数
int[][] dp = new int[steps+1][maxCol+1];
//初始化行 开始的时候步数为为0 只有dp[0][0]=1 其他都为0
dp[0][0]=1 ;
for (int i = 1; i <steps+1 ; i++) {//步数从1开始走，最多为steps
for (int j=0;j<maxCol+1;j++){
//当在0的位置时候 要想走到0 2种方法 从1跳到0 dp[i-1][1] 或者0到0 dp[i-1][0]
if(j==0) dp[i][j]=(dp[i-1][1]+dp[i-1][0]) % 1000000007;
//当在最右边的时候 要想走到最右边 2种方法 从j-1跳到j dp[i-1][j-1] 或者j到jdp[i-1][j]
else if(j==maxCol) dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]) % 1000000007;
//一般情况 走到该位置 可以是不动 左走 右走
else{ //上个位置向右走 左走 不动
dp[i][j]=((dp[i-1][j-1]+dp[i-1][j+1])%1000000007+dp[i-1][j]) % 1000000007;
}
}
}
return dp[steps][0] % 1000000007; //使用steps来到0位置的方法数
}
5.换钱的货币数
力扣地址：
public int waysToChange(int n) {
int[] coins = {1,5,10,25};
//dp[i][j]代表任意使用coins[0..i]能够拼成j钱数的方法数
int[][] dp=new int[4][n+1];
for (int j = 0; j < n + 1; j++)
dp[0][j]=1;
for (int i = 0; i < 4; i++)
dp[i][0]=1;
for(int i=1;i<coins.length;i++)
for(int j=1;j<n+1;j++){
//如果不用当前硬币 直接继承上面的总数
dp[i][j]=dp[i-1][j]%1000000007;
//如果使用当前硬币 看看超过没有
if(j-coins[i]>=0)
dp[i][j]+=(dp[i][j-coins[i]]%1000000007);
}
return dp[3][n]%1000000007;
}
6.机器人的路径和
public int uniquePaths(int m, int n) {
int[][] dp=new int[m][n];
dp[0][0]=1;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(i==0 || j==0) dp[i][j]=1;//当在边界的时候 只有一种方法可以走
else dp[i][j]=dp[i-1][j]+dp[i][j-1];//当前位置为前面或者上面方法之和
}
return dp[m-1][n-1];
}
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid[0][0]==1) return 0;
int row=obstacleGrid.length;
int col=obstacleGrid[0].length;
int[][] dp=new int[row][col];//dp[i]代表走到当前位置的路径有多少种
dp[0][0]=1;
//下面两个for循环 初始化边界
for (int i = 1; i < col; i++)
//当走得到前一个 且 当前位置不是障碍物 则当前位置置为1
if(dp[0][i-1]!=0 && obstacleGrid[0][i]!=1) dp[0][i]=1;
for (int i = 1; i < row; i++)
//当走得到上一个 且 当前位置不是障碍物 则当前位置置为1
if(dp[i-1][0]!=0 && obstacleGrid[i][0]!=1) dp[i][0]=1;
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
//当前位置不是障碍物
if(obstacleGrid[i][j]!=1){
//当前位置前面和上面情况相加就行
dp[i][j]=dp[i-1][j] +dp[i][j-1];
}
}
}
return dp[row-1][col-1];
}
public int minPathSum(int[][] grid) {
if(grid==null || grid.length==0 || grid[0].length==0) return 0;
int[][] dp=new int[grid.length][grid[0].length];
dp[0][0]=grid[0][0];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
//边界情况只能是左边dp[0][j-1]和当前位置相加
if(i == 0 && j!=0)
dp[i][j]=dp[i][j-1]+grid[i][j];
//边界情况只能是上边dp[i-1][0]和当前位置相加
else if(j==0 && i!=0)
dp[i][j]=dp[i-1][j]+grid[i][j];
//普通情况就是取上边或者左边最小的那种情况 然后加上当前的路径
else if(j!=0 && i!=0){
dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
}
return dp[grid.length-1][grid[0].length-1];
}
7.不同的二叉树
二叉树： 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
public int numTrees(int n) {
int[] dp=new int[n+1];
dp[0]=1;//0个节点 有1种
dp[1]=1;//1个节点 有1种
/*相当于把节点分为左右两部分 当左子树为0个 则右子树为n-1个 因为要把头结点去掉嘛
当左子树为1 则右子树为n-2 当左子树为2 则右子树为n-3
当左子树为j 则右子树为n-j-1 则 f(j)*f(n-j-1)种
*/
for (int i = 2; i <= n; i++) {
int way=0;
for(int j=0;j<i;j++){
way+=dp[j] * dp[i-j-1];
}
dp[i]=way;
}
return dp[n];
}
8.连续子数组最大和
- 思考状态：dp[i]代表着以nums[i]结尾的最大的子序列和。
- 思考状态转移方程：dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); 取dp[i-1]+nums[i]和nums[i]的最大值是因为考虑dp[i-1]是否对nums[i]产生了负增益，如果对nums[i]产生了负增益，那么不如不产生，对应的就是将dp[i-1]去掉，直接取nums[i]就行
- 思考初始化：dp[0] = nums[0]，所以i必须从1开始直到末尾。
public int maxSubArray(int[] nums) {
int max=nums[0];
int[] dp=new int[nums.length];
dp[0]=nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i]=Math.max(nums[i]+dp[i-1],nums[i]);
max=Math.max(max,dp[i]);
}
return max;
}
进阶：一个整型矩阵，返回子矩阵的最大累计和。
思想：上面求的是每一行的最大序列和。那么我们可以将二维数组第 i 行到第 j 行相同列的元素加起来，然后再当作一维数组来求解。假设有3行。则每次来到当前行可以划分为不同的排列。如假设当前在0行，则可以划分为第0行、第01行、第02行。然后遍历完成来到了第1行，则当前可以划分为第1行、第1~2行，遍历完成，然后来到第2行，则当前可以划分为第2行。就相当于把二维的进行压缩为一行这种。然后利用上述方法求得最大矩阵和
public static int maxSum(int[][] m) {
if (m == null || m.length == 0 || m[0].length == 0) return 0;
int max = Integer.MIN_VALUE;
int[] s = null;
for (int i = 0; i != m.length; i++) {
s = new int[m[0].length];//构造每一行的数组大小
for (int j = i; j < m.length; j++) {//来到当前行 都可以往后面进行组合
int curMax = 0;
for (int k = 0; k < s.length; k++)
s[k] += m[j][k];//依次填充每个元素
//每填充完一行 看看当前行的最大值是啥，取最大值 然后继续让当前行和下一行合并为新的一行
curMax=maxSubArray(s);
max=Math.max(curMax,max);
}
}
return max;
}
public static int maxSubArray(int[] nums) {
int max=nums[0];
int[] dp=new int[nums.length];
dp[0]=nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i]=Math.max(nums[i]+dp[i-1],nums[i]);
max=Math.max(max,dp[i]);
}
return max;
}
9.买股票的最佳时间
/**
* 记录【今天之前买入的最小值】
* 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
* 比较【每天的最大获利】，取最大值即可
*/
public int maxProfit(int[] prices) {
if(prices.length<=1) return 0;
int minPrice=prices[0],maxProfile=0;//定义最小的买入，最大的卖出
for (int i = 1; i < prices.length; i++) {
//让当天的利润和前面的最大利润做比较
maxProfile=Math.max(prices[i]-minPrice,maxProfile);
minPrice=Math.min(prices[i],minPrice);
}
return maxProfile;
}
10.爬楼梯
public int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
int[] f=new int[n+1];
f[1]=1;f[2]=2;
for (int i = 3; i <= n; i++)
f[i]=f[i-2]+f[i-1];
return f[n];
}
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}
/*dp[i]的定义：第i个台阶所花费的最少体力为dp[i]。
确定递推公式：可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
那么究竟是选dp[i-1]还是dp[i-2]呢？一定是选前面最小的 然后加上当前楼梯的花费
所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
*/
public int minCostClimbingStairs(int[] cost) {
if(cost.length==2) return cost[0]>cost[1]?cost[1]:cost[0];
int[] dp=new int[cost.length];
dp[0]=cost[0];
dp[1]=cost[1];
for(int i=2;i<cost.length;i++){
dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];
}
// 取倒数第一个数和第二个数的最少值 因为他们都可以跳出去的嘛
return Math.min(dp[cost.length-1],dp[cost.length-2]);
}
矩形覆盖：当 n 为 1 时，只有一种覆盖方法。当 n 为 2 时，有两种覆盖方法，可以看成斐波那契数列
```java public int rectCover(int target) { if(target<=2) return target; int[] f=new int[target+1];//数组大小 f[0]=1;f[1]=2; for (int i = 2; i <= target; i++) f[i]=f[i-1]+f[i-2]; return f[target-1];//由于我是从第0项开始算的，所以是target-1 } ```
11.除数博弈
//方法一
public boolean divisorGame(int n) {
if(n<2) return false;
boolean[] dp=new boolean[n+1];
dp[0]=false;
dp[1]=false;
dp[2]=true;
for(int i=3;i<=n;i++){
for (int j = 1; j <i ; j++) {
//每到了一个数就从1开始遍历到该数 看看当中是否有一个数满足i%j==0 且他的对手是false
if(i%j==0 && !dp[i-j]){
dp[i]=true;
break;
}
}
}
return dp[n];
}
//方法2
public boolean divisorGame1(int n) {
return n%2==0;
}
12.打家劫舍
因为不限定下标为 i 这一天是否接受预约，因此需要分类讨论：
1:接受预约，那么昨天就一定休息，就不能用 dp[i - 1] 的值，因为dp[i-1]涵盖了下标为 i - 1 这一天接收预约的情况的最大值，状态只能从下标为 i - 2 的状态转移而来：dp[i - 2] + nums[i]；
2:不接受预约，那么昨天可以休息，也可以不休息，状态从下标为 i - 1 的状态转移而来：dp[i - 1]；
二者取最大值，因此状态转移方程为 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。
public int rob(int[] nums) {
if(nums==null || nums.length==0) return 0;
if(nums.length==1) return nums[0];
int[] dp=new int[nums.length];
dp[0]=nums[0];//只有 1 天的时候，必须接受预约
//2天的时候，由于不能同时接受预约，因此最优值是这两天接受预约时长的最大值
dp[1]= Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++){
//今天选则昨天不能选，前天(i-2)可以选，今天不选，则昨天可以选，然后选择一个最优的
dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
}
//下标为 i 的这一天考虑了接受预约与不接受预约的情况，因此输出就是最后一天的状态值。
return dp[nums.length-1];
}
13.最长的有效括号
public int longestValidParentheses(String s) {
if(s==null || s.length()==0) return 0;
int[] dp=new int[s.length()];
dp[0]=0;
int max=0;
for (int i = 1; i < s.length(); i++) {
//如果当前是左括号 则到达该位置肯定不得行 匹配不上
if(s.charAt(i)=='(')
dp[i]=0;
//说明到达了右括号
else {
//往前走需要到达的匹配的位置 因为dp[i-1]已经是匹配好了
int pre=i-dp[i-1]-1;
//如果往前数的那个位置刚好是'('则匹配成功 +2 因为i-1已经匹配好了 所以还要加上dp[i-1]
if(pre>=0 && s.charAt(pre)=='('){
dp[i]=2+dp[i-1];
//如果pre=0,第一个字符肯定没有谁和他匹配 所以当pre>0 有可能 pre-1之前也有匹配好了的 所以还要加上dp[pre-1]
if(pre>0)
dp[i]+=dp[pre-1];
}
max=Math.max(max,dp[i]);
}
}
return max;
}
//eg：(())(()()) 当前来到最后一个位置 往前看 pre=4 刚好和最后一个匹配上则+2，然后再加上他们之间已经匹配好的4 就是6 然后pre-1的那个位置也匹配好了 则再加dp[pre-1]
14.接雨水（重点）
力扣地址:注意到下标 i 处能接的雨水量由 leftMax和rightMax 中的最小的挡板值决定。
eg:因为rightMax <leftMax 则此时应该从右往左遍历 发现11比7大 则不能接水 要流出去 为0，然后更新rightMax =11，此时11>10，则应该从左往右看，发现8<10则当前位置能接2滴水，然后更新leftMax 还是为10
public int trap(int[] height) {
if(height.length<=1) return 0;//两个格子绝对不可能接到水 始终会流出去
//leftMax rightMax记录当前位置的左边最大值和右边最大值
int res=0,leftMax=0,rightMax=0,l=0,r=height.length-1;
while (l<=r){
/*min{leftMax,rightMax} 代表取左右边最小的挡板 毕竟超了就要流出去嘛
min{leftMax,rightMax} -height[i]代表当前位置到底是高于两边还是低于两边
如果减出来结果为负数 则当前位置比两边高 不能接水 就是0，否则就为能够接的水数量
*/
//如果左边挡板比右边低 则当前应该从左边向右进行遍历
if(leftMax<=rightMax){
int receive=Math.min(leftMax,rightMax)-height[l];
if(receive<=0)
res+=0;
else res+=receive;
//更新左边的最大值
leftMax=Math.max(leftMax,height[l++]);
}else { //如果左边挡板比右边高 则当前应该从右边向左进行遍历
int receive=Math.min(leftMax,rightMax)-height[r];
if(receive<=0)
res+=0;
else res+=receive;
//更新右边的最大值
rightMax=Math.max(rightMax,height[r--]);
}
}
return res;
}
15.最长递增子串和序列
public int findLengthOfLCIS(int[] nums) {
if(nums.length<=1) return nums.length==0?0:1;
int[] dp=new int[nums.length]; //dp【i】代表以i结尾的最长子序列长度
dp[0]=1;
int max=0;
for(int i=1;i<nums.length;i++){
if(nums[i]>nums[i-1])
dp[i]=1+dp[i-1];
else
dp[i]=1;
max=Math.max(max,dp[i]);
}
return max;
}
高级版本 不连续的子序列：解法跟上面类似 只是不连续的话就需要往前遍历 来找到最长的递增子序列
public int lengthOfLIS(int[] nums) {
if(nums.length==1) return 1;
//dp【i】代表以i结尾的最长子序列长度
int[] dp=new int[nums.length];
dp[0]=1;
int max=1;
for (int i = 1; i <nums.length ; i++) {
dp[i]=1;//每次来到当前位置都是一个子序列 初始化为1
//每次来到当前位置 往前遍历 看看能不能找到小于当前元素的数据
//往前找 找到小于当前位置的元素的最大dp[i]
int curMax=0;
for (int j = i-1; j >=0 ; j--) {
if(nums[j]<nums[i])
curMax=Math.max(curMax,dp[j]);
}
dp[i]+=curMax;//加上前面的最大子序列
max=Math.max(dp[i],max);//取最大值
}
return max;
}
/* 解法2：贪心+二分查找
新建数组 cell，用于保存最长上升子序列。进行遍历，将每位元素二分插入 cell 中，注意cell数组严格上升，故可以使用二分查找。
如果 cell 中元素都比当前元素小，将它插到最后
否则，用当前元素覆盖掉比它大的cell数组中最小的那个。
总之，思想就是让 cell 中存储比较小的元素。注意：cell 未必是真实的最长上升子序列，但长度是对的!
*/
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n <= 1) return n;
// cell存储比较小的元素 用于保存最长上升子序列
int[] cell = new int[n];
cell[0] = nums[0];
// ans记录最长连续递增子序列的结束索引
int ans = 0;
for (int i = 1; i < n; i++) {
int l = 0, r = ans;
if (nums[i] > cell[ans]) {
ans++;
cell[ans] = nums[i];
} else {
while (l < r) {
int mid = l + ((r - l)/2);
if (nums[i] > cell[mid])
l = mid + 1;
else
r = mid;
}
cell[l] = nums[i];
}
}
return ans + 1;
}
进阶版 最长递增子序列的最小字典序
16.最小编辑代价
力扣地址：经典动态规划方法，利用二维数组dp[][]保存动态规划表
假设str1长度为M[0…M-1]，str2长度为N[0…N-1]，dp大小为(M+1)*(N+1)；
dp【i】【j】表示str1[0…i-1]编辑成str2[0…j-1]的最小编辑代价，dp大小为(M+1)*(N+1)是为了从空串开始计算，即dp【0】【0】表示空串编辑到空串的最小编辑代价。
/*如何生成dp[][]: ic，dc和rc，分别代表插入、删除和替换一个字符的代价
1.dp[0][0]表示空串编辑成空串，故dp[0][0]=0; 0种方法
2.求第一行dp[0][j]，表示空串编辑成str2[0....j-1]，只能插入 则dp[0][j]=ic*j;
3.求第一列dp[i][0]，表示str1[0......i-1]编辑成空串，只能删除 则dp[i][0]=dc*i;
4.求dp[i][j]，即str1[0....i-1]编辑成str2[0.....j-1]，四种可能的途径：
<1> str1[0....i-1]先编辑成str2[0.....j-2]，这个时候还少一个元素 则再添加就行 也就是再由str2[0.....j-2]到str2[0.....j-1]，即dp[i][j-1]+ic; eg:s1:aqqcde s2:adcd 我先让aqqcde变成abc 然后再加上d 就变成了abcd 即dp[i][j-1]+ic 也就是先让s1变成j-1之前的字符串 然后再add
<2> str1[0....i-1]先编辑成str1[0.....i-2]，再由str1[0.....i-2]到str2[0.....j-1]，即dp[i-1][j]+dc; eg: s1:aqqcde s2:adcd 让aqqcd变成s2的abcd 然后删除s1的e 即dp[i-1][j]+dc
<3> 让str[0..i-1]变成str2[0..j-1] 然后当前字符进行替换rc就行 dp[i-1][j-1]+rc
eg:s1:aqqcde s2:adcd 先让aqqcd变成adc 然后e替换为c 即dp[i-1][j-1]+rc
<4> 如果str1[i-1]==str2[j-1],意思就是当前2个字符本来就相等了又因为前面的编辑好了 则当前不需要编辑 即dp[i][j]=dp[i-1][j-1];
然后取4者的最小值
*/
public int minDistance(String word1, String word2) {
int row=word1.length();
int col=word1.length();
int[][] dp=new int[row+1][col+1];
//从 空串替换为 word2 的方法数 第0行只能进行添加
for (int i = 0; i < col+1; i++)
dp[0][i]=i;
//从 word1替换为 空串 的方法数 第0列只能进行删除
for (int i = 0; i < row+1; i++)
dp[i][0]=i;
for (int i = 1; i <row+1 ; i++) {
for (int j = 1; j <col+1 ; j++) {
//如果当前字符相等 则可以不进行替换
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j]=dp[i-1][j-1];
else //如果不相等 假设前面的字符相等 然后当前字符进行替换
dp[i][j]=dp[i-1][j-1]+1;
/*
horse 变为了 ro 然后再添加s dp[i][j]=dp[i][j-1]+1;
horse 的hors变为了 ro 然后再删除e dp[i][j]=dp[i-1][j]+1;
删除和添加的最小值
*/
int addOrDel=Math.min(dp[i][j-1]+1,dp[i-1][j]+1);
//然后addOrDel再和替换的最小值中取最小值
dp[i][j]=Math.min(dp[i][j],addOrDel);
}
}
return dp[row][col];
}
17.零钱兑换
//方法一
public int coinChange(int[] coins, int amount) {
if(amount==0) return 0; //0块钱 怎么都莫法拼
//dp[i][j]代表任意使用硬币coins【0..i】能够拼出的j钱的方法
int[][] dp=new int[coins.length][amount+1];
//初始化第0行 使用第一个硬币 看看能不能拼出从1..amount的钱数 不能拼置为最大值表示无解
for (int i = 1; i <amount+1 ; i++)
if(i%coins[0]==0)dp[0][i]=i/coins[0];
else dp[0][i]=Integer.MAX_VALUE;;
//初始化第0列 当amount=0时候 全为0 由于数组默认是0 所以这里我们就不用初始化了
for (int i = 1; i <coins.length ; i++) {
for (int j = 1; j < amount+1; j++) {
//当不使用当前硬币 则直接继承dp[i-1][j]
dp[i][j]=dp[i-1][j];
//当使用当前硬币 则j-coins[i]*count coins[i]*count 代表当前硬币使用了count次能够拼出的钱数
// j-coins[i]*count 代表已经用了当前硬币 则前面必须用j-coins[i]*count才行 且不能越界
//但是画出二维表可以发现 dp[i][j-coins[i]]=sum【dp[i-1][j-coins[i]*count]】因为上面是继承的关系啊
// 想到这 下面可以优化为一维表
if(j-coins[i]>=0)
if(dp[i][j-coins[i]]!=Integer.MAX_VALUE)
dp[i][j]=Math.min(dp[i][j-coins[i]]+1,dp[i][j]);
}
}
return dp[coins.length-1][amount]==Integer.MAX_VALUE?-1:dp[coins.length-1][amount];
}
//方法二 优化为一维表 相当于竖起填二维表并且压缩为一行 代表当前使用任意种硬币拼成i的最少方式
public int coinChange(int[] coins, int amount) {
int[] dp=new int[amount+1];//dp[i]表示能够拼凑i的最小方式
dp[0]=0; //初始化为当钱数为0的时候 方法为0
for (int i = 1; i <= amount; i++) {
dp[i]=Integer.MAX_VALUE;//每次来到当前位置先置为最大值表示无解
//遍历硬币 假设当前有3种 则i-coins[j]表示使用当前coins[j]硬币后 前面能够拼成i-coins[j]的最少方式 再+1取最小值即可
// dp[i]=min{dp[i-coins[0]]+1,dp[i-coins[1]]+1,f[dp-coins[2]]+1}
for (int j = 0; j < coins.length; j++)
if(i-coins[j]>=0 && dp[i - coins[j]] != Integer.MAX_VALUE )
dp[i]=Math.min(dp[i-coins[j]]+1,dp[i]);
}
return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}
}
18.两个字符串的最长公共子串和子序列
1.最长公共子串
牛客地址：子串 则要连续 注意：最长公共子串必须以i和j结尾，如果i和j的字符不相等 则当前位置直接置为0，如果相等 则继承左上方的值
//方法一 直接二维空间 每个值依赖左上角的值
public String LCS (String str1, String str2) {
//dp[i][j]代表必须以i结尾的str1和必须以j结尾的str2的最长公共子串大小
//注意 最长公共子串必须以i和j结尾
int[][] dp=new int[str1.length()][str2.length()];
//初始化第0行 看看str1[0]和str2的结尾字符是否一样 一样就是1 不一样就是0
for (int i = 0; i < str2.length(); i++)
if(str1.charAt(0)==str2.charAt(i)) dp[0][i]=1;
//同上逻辑
for (int j = 0; j < str1.length(); j++)
if(str1.charAt(j)==str2.charAt(0)) dp[j][0]=1;
int max=0,endMax=0;
for (int i = 1; i < str1.length(); i++) {
for (int j = 1; j < str2.length(); j++) {
//看看当前位置是否一样 如果一样 则继承dp[i-1][j-1]再加上当前位置
if(str1.charAt(i)==str2.charAt(j))
dp[i][j]=dp[i-1][j-1]+1;
/*如果不一样 则直接为0 因为上面定义的就是最长公共子串必须以i和j结尾
i和j位置的字符都不一样 则肯定为0 因为数组默认就是0 所以不操作就行*/
if(dp[i][j]>max){
max=dp[i][j];//更新最大值
endMax=i;//更新最大子串是在哪结尾的
}
}
}
return str1.substring(endMax-max+1,endMax+1);
}
//方法二 空间压缩 发现没有 上面那张继承逻辑 已经出来了 那么我们从右上方 按斜线一个一个往左下方填
public String LCS2 (String str1, String str2) {
char[] chs1 = str1.toCharArray();
char[] chs2 = str2.toCharArray();
int row = 0;
int col = chs2.length - 1;
int max = 0,end = 0; //max最大值 end最大值在哪结束
//当遍历到左下角就相当于填二维表完成了
while (row < chs1.length) {
int i = row,j = col;
int curMax = 0;
//边界条件 遍历是左上方往右下方成斜线遍历 当超过斜线的范围 则遍历结束
while (i < chs1.length && j < chs2.length) {
if (chs1[i] != chs2[j]) curMax = 0;//如果当前字符不相等 则还是为0
else curMax++;//相等了 则当前最大值curMax++
//加完之后 更新最大值
if (curMax > max) {
end = i;
max = curMax;
}
i++;
j++;
}
//更新列或者行 让它从正确的起始位置 斜起遍历
if (col > 0)
col--;
else
row++;
}
return str1.substring(end - max + 1, end + 1);
}
2.最长公共子序列
力扣地址 牛客地址：子序列不同于子串 子序列可以不连续 子串必须连续
//最长公共子序列
public int longestCommonSubsequence(String text1, String text2) {
//dp[i][j] s1(0..i)和s2(0..j)的最长子序列 当中可以不包含i和j的字符
int[][] dp=new int[text1.length()][text2.length()];
//第一行 由于只有一行 则 要么是0 要么是1
dp[0][0]=text1.charAt(0)==text2.charAt(0)?1:0;
for (int j = 1; j < text2.length(); j++)
if(text1.charAt(0)==text2.charAt(j))
dp[0][j]=1;
else dp[0][j]=dp[0][j-1];//如果不相等 继承左边
for (int i = 1; i < text1.length(); i++)
if(text1.charAt(i)==text2.charAt(0))
dp[i][0]=1;
else dp[i][0]=dp[i-1][0];//如果不相等 继承上边
for (int i = 1; i < text1.length(); i++) {
for (int j = 1; j < text2.length(); j++) {
//四种情况
//1 无i和j位置的字符都参加 则说明与i-1和j-1相关 dp[i][j]=dp[i-1][j-1]
//2 有i位置参与 无j位置参与 则说明与i和j-1相关 dp[i][j]=dp[i][j-1]
//3 无i位置参与 有j位置参与 则说明与i-1和j相关 dp[i][j]=dp[i-1][j]
//4 有i j都参与 则前提s1[i]==s2[j] dp[i][j]=dp[i-1][j-1]+1
//取4种方案的最大值
dp[i][j]=Math.max(dp[i-1][j-1],dp[i][j-1]);
dp[i][j]=Math.max(dp[i-1][j],dp[i][j]);
if(text1.charAt(i)==text2.charAt(j))
dp[i][j]=Math.max(dp[i-1][j-1]+1,dp[i][j]);
}
}
return dp[text1.length()-1][text2.length()-1];
}
3.公共子序列的变种题
不想交的线：思想跟求最长公共子序列的思想一样
19.最长回文子串和序列
1.最长回文子串
力扣地址：中心扩散 和动态规划来做 中心扩散就不用介绍了。动态规划的话可以把这个这个字符串反转成str1。然后就可以求str和str1的最长公共子串啦 中心扩散代码如下：
//找到每个下标 然后往两边进行扩散找到最大回文串 由于此种方法有奇偶性的问题 所以给每个字符的前后端加上一个特殊符号进行处理，处理完成之后，最大的回文子串的中心位置center就是新串index/2。
public String longestPalindrome(String s) {
if(s== null || s.length()==1) return s;
StringBuilder sb=new StringBuilder();
sb.append("#");
int count=1,j=0;
//处理字符串 babad--> #b#a#b#a#d 这样就把偶数和奇数进行处理了，
while(j<s.length()){
if(count%2==0) sb.append("#");
else sb.append(s.charAt(j++));
count++;
}
String str=sb.append("#").toString();//结尾处再加上一个#
int max=1,maxIndex=0;
for(int i=0;i<str.length();i++){
int left=i-1,right=i+1,curMax=1;//因为当前位置一个数也是回文，所以初始化为1
//从当前位置往两边进行扩散判断
while(left>=0 && right<str.length()){
//如果两边相等了 就+2 然后继续循环，否则不相等了直接跳出循环
if(str.charAt(left) == str.charAt(right)) {
curMax+=2;
left--;
right++;
}
else break;
}
//跳出循环之后 判断当前位置的最大回文数是否超越了上一个，超过了就更新最大值和最大下标
if(curMax>max){
max=curMax;
maxIndex=i;
}
//如果最大值直接等于了字符串的长度 那么也没有继续循环比较的必要了 直接跳出循环
if(max==str.length()) break;
}
//然后开始切割字符串 #b#a#b#a#d max / 2相当于就是半径的意思
String s1 = str.substring(maxIndex - max / 2, maxIndex + max / 2);
return s1.replaceAll("#", "");//然后把#去除掉 就是最大回文子串了
}
2.最长回文子序列
力扣地址：
方法一：可以把这个这个字符串反转成str1。然后就可以求str和str1的最长公共子序列啦
方法二：这里我用另一种dp思路 范围尝试：以i开始j结尾进行分四种情况 。
public int longestPalindromeSubseq(String s) {
int length = s.length();
//dp[i][j]表示str i..j位置上的最长回文序列长度
//则二维表创建好了后 只有右上方的值才有效 左下方的全部废掉 因为i不能超过j
//则最右上方的值 就是str[0..length]的最大回文串长度 dp[0][length-1]
int[][] dp=new int[length][length];
for (int i = length-1; i >=0 ; i--) {
for (int j = i; j <length; j++) {
//来到了对角线i==j位置 一个字符就是一个回文串 则str[i]=str[j]当前长度就为1
if(i==j) dp[i][j]=1;
//如果只有2个字符 则看这两个字符是否一样 一样则为2 不一样则为1
else if(i+1==j){
if(s.charAt(i)==s.charAt(j)) dp[i][j]=2;
else dp[i][j]=1;
}
//上面是两个base case 下面就是一般的状态转移
else {
//4中情况 取最大值
// 1：最大回文串不以i开始 不以j结尾 则中间字符串就是最大 dp[i+1][j-1]
// 2：最大回文串以i开始 不以j结尾 dp[i][j-1]
// 3：最大回文串不以i开始 以j结尾 dp[i+1][j]
// 4：最大回文串以i开始 以j结尾 前提条件 s[i]==s[j] dp[i+1][j-1]+2 也就是第一种情况下+2
dp[i][j]=Math.max(Math.max( dp[i+1][j-1],dp[i][j-1]),dp[i+1][j]);
if(s.charAt(i)==s.charAt(j)) dp[i][j]=Math.max(dp[i][j],dp[i+1][j-1]+2);
}
}
}
return dp[0][length-1];
}
20.添加字符变成回文串
力扣地址：
方法一：换个角度想:当前字符串要变成回文,那只要把不一样的找出来就好了。即:求出反过来的字符串和当前字符串的最长公共子序列，或者换个角度 求字符串的最长回文子序列 然后总长度减去这个最大长度 反正25题和26题都是一个意思
如：“ab” --> reverse —> “ba”, “ab"和"ba"的 最长公共子序列长度是 1, 而字符串的长度= 2, 2 - 1 = 1, 即 只插入1个字母就好咯。 “aba” 或者"bab”.
如：leetcode 和 edocteel 的最长公共子序列是 e t e ,长度为3, 即 8-3 = 5。
方法二：填格子的大致状态跟最长回文子序列一样 但是转移方程不一样 因为尝试状态不同 这道题尝试状态有3种
public int minInsertions(String s) {
//dp[i][j]代表str[i..j]最少插入的次数
int[][] dp=new int[s.length()][s.length()];
//跟最长回文子序列一样 从下往上填
for (int i = s.length()-1; i >=0 ; i--) {
for (int j = i; j <s.length() ; j++) {
if(i==j) dp[i][j]=0;//如果i=j说明只有一个字符 当前字符就是回文串 不需要添加
else if(i+1==j){//如果i+1=j说明有2个字符
if(s.charAt(i)!=s.charAt(j)) dp[i][j]=1;//当前2个字符不相等 需要添加1个 相等 就不需要添加
//由于数组默认就是0 所以不操作
}
//通常情况
else {//分4种情况 取最小值
//1.回文串以i开始 j-1结束 然后由于多了一个j 所以在i-1的位置添加上j的字符即可 dp[i][j-1]+1
//2.回文串以i+1开始 j结束 然后由于多了一个i 所以在j+1的位置添加上i的字符 dp[i+1][j]+1
//3.回文串以i+1开始 j-1结束 但是i和j不相等则需要添加2个字符 dp[i+1][j-1]+2
//4.回文串以i+1开始 j-1结束 但i和j相等 则需要添加0个字符 前提s[i]=s[j] dp[i+1][j-1]+0
dp[i][j]=Math.min(Math.min(dp[i+1][j]+1,dp[i][j-1]+1),dp[i+1][j-1]+2);
if(s.charAt(i)==s.charAt(j)) dp[i][j]=Math.min(dp[i][j],dp[i+1][j-1]);
}
}
}
return dp[0][s.length()-1];
}
21.分割回文串
1.分割回文串 返回所有结果（暂未解决）
2.分割回文串的最小次数
力扣地址：返回分割的最小次数
//分割回文串 最小分割次数
public static int minCut(String s) {
//获取str[i..j]位置是不是回文
boolean[][] isHuiWen = getIsHuiWen(s);
int[] dp=new int[s.length()];//dp[i]:dp[0..i]的最小回文分割数
//dp[0]=0;由于数组默认初始化就是0 所以不用写
for (int i = 1; i <s.length() ; i++) {
//如果str[0..i]是回文串 则不需要处理 直接是0
//如果str[0..i]不是回文串 则需要取最小分割的情况
if(!isHuiWen[0][i]){
dp[i]=Integer.MAX_VALUE;
/**
* 要对长度为[0, i]的子串进行分割，分割点为j。那么分割后，如果str[j + 1, i]是回文子串，那么dp[i]=dp[j] + 1。
为什么只看[j + 1, i]区间，不看[0, j]区间是不是回文子串呢？
解释：dp[i]表示范围是[0, i]的回文子串，最少分割次数是dp[i]。
[0,j]区间的最小切割数量，我们已经知道了就是dp[j]。而str[j+1,i]是回文串 则这1刀直接从j和j+1之间的空隙切下去 需要一刀
所以就是dp[j]+1;就比如 aa bcb 则从j=1位置切下去 两边都是回文串
*/
for (int left = 0; left < i; left++) {
if(isHuiWen[left+1][i])
dp[i]=Math.min(dp[i],dp[left]+1);
}
}
}
return dp[s.length()-1];
}
//获得一个boolean数组 判断从str[i..j]是不是回文串
public static boolean[][] getIsHuiWen(String s){
//dp[i][j] 代表str[i..j]是不是回文串 则二维表左下角废掉
boolean[][] dp=new boolean[s.length()][s.length()];
for (int i = s.length()-1; i >=0 ; i--) {
for (int j = i; j <s.length() ; j++) {
if(i==j) dp[i][j]=true;//str[i..i]一个字符 肯定是回文
else if(i+1==j){//当2个字符的时候 看看这2个字符相不相等
if(s.charAt(i)==s.charAt(j)) dp[i][j]=true;
}
else {
if(s.charAt(i)==s.charAt(j)) //如果当前字符相等了 看看i+1..j-1是不是回文串
dp[i][j]=dp[i+1][j-1] && true;
else dp[i][j]=false;//当前字符不相等 则肯定不是回文串
}
}
}
return dp;
}
22.正则表达式匹配
public boolean isMatch(String s, String p) {
if (s.length() == 0 && p.length() == 0) return true;
int row = s.length();
int col = p.length();
//dp[i][j]代表 s[0..i-1]和p[0..j-1]能够匹配上 特别注意：这里我是从i=1开始的 所以要减1
boolean[][] dp = new boolean[row + 1][col + 1];
dp[0][0] = true;//2个都为空串 肯定true
// 初始化第0行 当s为空串的时候
for (int j = 1; j < col + 1; j++) {
if (j == 1) dp[0][j] = false;//p有一个字符的时候 不管怎么样 绝对莫法匹配
else {//当前位置(j-1)是*，不需要看前一个字符 因为前一个字符加上*可以变为空串
// 而是要看前两个字符那个位置是不是true 即dp[0][j-2]，要看之前的能否匹配
//比如a*b*下标依次为ftft，b之前的位t，所以j-1也是true
if (p.charAt(j - 1) == '*' && dp[0][j - 2]) dp[0][j] = true;
}
}
// 初始化第0列 当p为空串的时候 无法匹配 默认false
//正常情况
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < col + 1; j++) {
//大体分3种情况
//1.当前字符相等 或者当前字符为'.' 则看s[0..i-1]和p[0..j-1]的情况怎么样
//如果都匹配不上 则当前肯定无法匹配 如果前面为true 当前又满足条件 则当前也为true
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')
dp[i][j] = dp[i - 1][j - 1];
//2.当前字符为*
else if (p.charAt(j - 1) == '*') {
if (j < 2) dp[i][j] = false;//当p第一个字符就是* 不符合要求 为false
/* 如果*前面的那个字符能够和s当前字符匹配上 则分3种情况 3种情况取或运算
①：*和前一个字符组成空串 就看*的前两个字符的状态是什么 也就是把*和前一个字符丢掉p[0..j-2]已经能够匹配上s[0..i]啦 即dp[i][j]=dp[i][j-2]
②：*和前一个字符只匹配一个 也就是把*和前一个字符默认匹配上s[i]啦，就相当于不要当前这个*了 dp[i][j]=dp[i][j-1]
也可以写成dp[i-1][j - 2] 就是p这2个字符不要了 s这个字符不要了 看看p[0..j-2]能不能匹配s[0..i-1]
③：*和前一个字符匹配多个 比如aabb aab* b*匹配了bb两个b 那么看aab和aab*是否能匹配上就行了，即dp[i][j]=dp[i-1][j]
*/
else if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')
dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
//如果*前边字符和s当前字符不匹配 那就把*和*前边一个字符都不要了
else if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.')
dp[i][j] = dp[i][j - 2];
}
//3.当前字符又不相等 也不是* 则无法匹配
else dp[i][j] = false;
}
}
return dp[row][col];
}
23.乘积最大子数组
public int maxProduct(int[] nums) {
if(nums.length==1) return nums[0];
//dp[i]以nums[i]结尾的子数组的 最大或者最小值
//为什么要记录最小值呢？因为最小值可能翻身变最大值
int[] maxDp=new int[nums.length];
int[] minDp = new int[nums.length];
maxDp[0]=nums[0];
minDp[0]=nums[0];
int max=nums[0];
for(int i=1;i<nums.length;i++){
//跟最大子数组和一样 每次更新完之后 更当前值进行比较 看是否产生了负收益
// 与自己进行比较是为了防止之前乘积结果为0 如果不比较后面乘积不管最大最小都会变成为0
//如果该元素为正数：如果到上一个元素为止的最大乘积也是正数，那么直接乘上就好了，同样的最大乘积也会变得更大
//如果该元素为负数：如果到上一个元素为止的最大乘积也是负数，那么直接乘上就好了，同样的最大乘积也会变得更大
maxDp[i]=Math.max(nums[i],Math.max(maxDp[i-1]*nums[i],minDp[i-1]*nums[i]));
minDp[i]=Math.min(nums[i],Math.min(maxDp[i-1]*nums[i],minDp[i-1]*nums[i]));
max=Math.max(maxDp[i],max);
}
return max;
}
24.不同的子序列
力扣地址：字符串 s 和字符串 t ，计算在 s 的子序列中 t 出现的个数。也就是有多少种删除的方法可以让s变成t。字符串的一个子序列 是指，通过**删除一些（也可以不删除）**字符且不干扰剩余字符相对位置所组成的新字符串。
public int numDistinct(String s, String t) {
if(s.length()==0 || t.length()==0) return 0;
//dp[i][j]代表s[0..i]能够变成t[0..j]的方法数
int[][] dp=new int[s.length()+1][t.length()+1];
//第0列 t为空串，空串是所有字符串的子集 题目说可以删除一些
for (int i = 0; i < s.length() + 1; i++) dp[i][0]=1;
//第0行 s为空串，空串不能再删除了 除了dp[0][0]=1 所以第0行全是0 默认就是0
for (int i = 1; i < s.length()+1; i++) {
for (int j = 1; j < t.length()+1; j++) {
//当j比i大 说明t的字符串比s长 s肯定莫法删除字符变成和t一样长 相当于二维表的右上方全部废掉
if(j>i) continue;
//如果当前i j字符相等 因为我是从1开始遍历的 所以i-1为当前字符
/*eg：s = "rara" t = "ra" ，当i = 3, j = 1时，s[i] == t[j]。
2种情况求和：
①：如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
②：如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]*/
else if(s.charAt(i-1)==t.charAt(j-1))
dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
//如果不相等 eg: s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j]
//此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的 dp[i-1][j]
else
dp[i][j] = dp[i-1][j];
}
}
return dp[s.length()][t.length()];
}
25.丑数
public int GetUglyNumber_Solution(int index) {
if(index<=0) return index;
int i2 = 0, i3 = 0, i5 = 0;
int[] dp = new int[index];
dp[0] = 1;
//第一个丑数是1，以后的丑数都是基于前面的小丑数分别乘2，3，5构成的
//我们每次添加一个当前计算出来个三个丑数的最小的一个，并且是谁计算的，谁指针就后移一位。
for (int i = 1; i < index; i++) {
int next2 = dp[i2] * 2;
int next3 = dp[i3] * 3;
int next5 = dp[i5] * 5;
dp[i] = Math.min(next2, Math.min(next3, next5));
// 这里不用else if的原因是有可能id2(3) * 2 == id3(2) * 3
// 这种情况两个指针都要后移
if (dp[i] == next2) i2++;
if (dp[i] == next3) i3++;
if (dp[i] == next5) i5++;
}
return dp[index - 1];
}
戳气球(太难了)
力扣地址：放个别人写的代码
class Solution {
public int maxCoins(int[] nums) {
int len=nums.length;
if(len==1) return nums[0];
//两头放哨兵1,后续可以不用做边界判断
int[] myNums = new int[len+2];
myNums[0] = 1;
myNums[len+1] = 1;
System.arraycopy(nums,0,myNums,1,len);
//dp矩阵多+2,和后续的i,j适配,坐标不用做转换 dp[i][j] 表示戳破区间a[i..j] 气球得到的最大分数
int[][] dp = new int[len+2][len+2];
//长度遍历,从底向上,1~len
/**
* 因为大区间可以划分成小区间，我们可以先计算小区间，然后再计算大区间。具体来说就是：
*对于区间 [i…j] ，枚举气球的位置，假设为 k ( i ⩽ k ⩽ j )，将区间分成两个子区间：[i…k-1] 和 [k+1…j]
* 对每个位置的划分，计算该种划分的分数： dp[i][k −1] + dp[k + 1] [j] + a[k] ∗ a [i−1] ∗ a [j+1] ，选择最大的分数即可。
* 思想:先爆破小区间，然后再爆破指定气球，而不是先爆破指定气球，再从剩下的气球中去任选一个去爆破。\
*/
for (int tempLen = 1; tempLen <= len; tempLen++) {
//左侧i坐标遍历,因为有哨兵,所以从1开始
for (int i = 1; i <= len - tempLen + 1; i++) {
int j = i + tempLen - 1;
//选在i,j范围内,戳破第k个
for (int k = i; k <= j; k++) {
// {i,k - 1}k{k + 1,j}
// 戳破k后,分别计算k左边myNums[i][k - 1],k右边myNums[k + 1][j]的继续戳,在加上戳k的得分
// 因为先计算了小长度的,在计算大的长度时,可以直接用小长度的结果,相当于缓存的效果
dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + myNums[k] * myNums[i - 1] * myNums[j + 1]);
}
}
}
return dp[1][len];
}
}
看看就行（我还是写不来啊）
1.跳马
/**
* 象棋中马的跳法【题目】请同学们自行搜索或者想象一个象棋的棋盘，
* 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置。那么整个棋盘就是横坐标上9条线、纵坐标上10条线的一个区域。
* 给你三个参数，x，y，k，返回如果“马”从(0,0)位置出发，必须走k步，最后落在(x,y)上的方法数有多少种？
*/
private static int HouseJumpDP(int x, int y, int step) {
//一个体 高是step 本层的结果依赖下一层，第0层会因为basecase推导出来，所以从第一层开始往上推
棋盘 横9【0，8】竖10【0，9】
if (x<0 || x>8 ||y<0 || y>9||step<0){
return 0;
}
int[][][] dp = new int[9][10][step + 1];
dp[0][0][0] = 1; //第0层的面只有（0，0）是1，其余全是0
for (int h = 1; h <= step; h++) { //从第一层开始
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 10; c++) {//x,y维度上的顺序无所谓，关键是高度要从低向上
dp[r][c][h] += getValue(dp, r - 1, c + 2, h - 1);
dp[r][c][h] += getValue(dp, r + 1, c + 2, h - 1);
dp[r][c][h] += getValue(dp, r + 2, c + 1, h - 1);
dp[r][c][h] += getValue(dp, r + 2, c - 1, h - 1);
dp[r][c][h] += getValue(dp, r + 1, c - 2, h - 1);
dp[r][c][h] += getValue(dp, r - 1, c - 2, h - 1);
dp[r][c][h] += getValue(dp, r - 2, c - 1, h - 1);
dp[r][c][h] += getValue(dp, r - 2, c + 1, h - 1);
}
}
}
return dp[x][y][step];//我想要的是x,y,step位置上的值
}
//防止越界 想象这个立方体泡在一个全是0的池子里，一旦越界返回0，不越界返回该位置的值
public static int getValue(int[][][] dp, int row, int col, int step) {
if (row < 0 || row > 8 || col < 0 || col > 9) {
return 0;
}
return dp[row][col][step];
}
2.最多区间异或和为0
public static int mostEOR(int[] arr) {
int ans = 0;
int xor = 0;
int[] mosts = new int[arr.length];
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for (int i = 0; i < arr.length; i++) {
xor ^= arr[i];
if (map.containsKey(xor)) {
int pre = map.get(xor);
mosts[i] = pre == -1 ? 1 : (mosts[pre] + 1);
}
if (i > 0) {
mosts[i] = Math.max(mosts[i - 1], mosts[i]);
}
map.put(xor, i);
ans = Math.max(ans, mosts[i]);
}
return ans;
}
3.表达式组成方案
牛客地址 0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成 的字符串express，再给定一个布尔值 desired。返回express能有多少种组合 方式，可以达到desired的结果
public static boolean isValid(char[] exp) {
if ((exp.length & 1) == 0) {
return false;
}
for (int i = 0; i < exp.length; i = i + 2) {
if ((exp[i] != '1') && (exp[i] != '0')) {
return false;
}
}
for (int i = 1; i < exp.length; i = i + 2) {
if ((exp[i] != '&') && (exp[i] != '|') && (exp[i] != '^')) {
return false;
}
}
return true;
}
public static int num2(String express, boolean desired) {
if (express == null || express.equals("")) return 0;
char[] exp = express.toCharArray();
//合法校验 看看数字是不是在0 2 4 6..位置上 看看符号在不在1 3 5 7..上 如果不满足则直接返回0
if (!isValid(exp)) return 0;
int[][] t = new int[exp.length][exp.length];
int[][] f = new int[exp.length][exp.length];
t[0][0] = exp[0] == '0' ? 0 : 1;
f[0][0] = exp[0] == '1' ? 0 : 1;
for (int i = 2; i < exp.length; i += 2) {
t[i][i] = exp[i] == '0' ? 0 : 1;
f[i][i] = exp[i] == '1' ? 0 : 1;
for (int j = i - 2; j >= 0; j -= 2) {
for (int k = j; k < i; k += 2) {
if (exp[k + 1] == '&') {
t[j][i] += t[j][k] * t[k + 2][i];
f[j][i] += (f[j][k] + t[j][k]) * f[k + 2][i] + f[j][k] * t[k + 2][i];
} else if (exp[k + 1] == '|') {
t[j][i] += (f[j][k] + t[j][k]) * t[k + 2][i] + t[j][k] * f[k + 2][i];
f[j][i] += f[j][k] * f[k + 2][i];
} else {
t[j][i] += f[j][k] * t[k + 2][i] + t[j][k] * f[k + 2][i];
f[j][i] += f[j][k] * f[k + 2][i] + t[j][k] * t[k + 2][i];
}
}
}
}
return desired ? t[0][t.length - 1] : f[0][f.length - 1];
}
(异或)五种字符组成 的字符串express，再给定一个布尔值 desired。返回express能有多少种组合 方式，可以达到desired的结果
```java
public static boolean isValid(char[] exp) {
if ((exp.length & 1) == 0) {
return false;
}
for (int i = 0; i < exp.length; i = i + 2) {
if ((exp[i] != '1') && (exp[i] != '0')) {
return false;
}
}
for (int i = 1; i < exp.length; i = i + 2) {
if ((exp[i] != '&') && (exp[i] != '|') && (exp[i] != '^')) {
return false;
}
}
return true;
}
public static int num2(String express, boolean desired) {
if (express == null || express.equals("")) return 0;
char[] exp = express.toCharArray();
//合法校验 看看数字是不是在0 2 4 6..位置上 看看符号在不在1 3 5 7..上 如果不满足则直接返回0
if (!isValid(exp)) return 0;
int[][] t = new int[exp.length][exp.length];
int[][] f = new int[exp.length][exp.length];
t[0][0] = exp[0] == '0' ? 0 : 1;
f[0][0] = exp[0] == '1' ? 0 : 1;
for (int i = 2; i < exp.length; i += 2) {
t[i][i] = exp[i] == '0' ? 0 : 1;
f[i][i] = exp[i] == '1' ? 0 : 1;
for (int j = i - 2; j >= 0; j -= 2) {
for (int k = j; k < i; k += 2) {
if (exp[k + 1] == '&') {
t[j][i] += t[j][k] * t[k + 2][i];
f[j][i] += (f[j][k] + t[j][k]) * f[k + 2][i] + f[j][k] * t[k + 2][i];
} else if (exp[k + 1] == '|') {
t[j][i] += (f[j][k] + t[j][k]) * t[k + 2][i] + t[j][k] * f[k + 2][i];
f[j][i] += f[j][k] * f[k + 2][i];
} else {
t[j][i] += f[j][k] * t[k + 2][i] + t[j][k] * f[k + 2][i];
f[j][i] += f[j][k] * f[k + 2][i] + t[j][k] * t[k + 2][i];
}
}
}
}
return desired ? t[0][t.length - 1] : f[0][f.length - 1];
}
版权声明：本文为weixin_45017459原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。