devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode刷题（动态规划篇）_跳1步 2步 递推 code

作者：IT小白 | 2024-02-10 13:49:19

赞

踩

跳1步 2步 递推 code

1.爬楼梯

1.确定dp数组以及下标的含义

dp[i]： 爬到第i层楼梯，有dp[i]种方法

2.确定递推公式

如果可以推出dp[i]呢？

从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来。

首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和。

因为到dp就两种了。dp[i-1]再走一步。dp[i-2],再走两步。

3.dp数组如何初始化

不初始化第0步，从第1和第2步开始。

4.确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         int dp[]=new int[n+1];
  4.         if(n==1){
  5.             return 1;
  6.         }
  7.         if(n==2){
  8.             return 2;
  9.         }
  10.    int i=3;
  11.    dp[1]=1;
  12.    dp[2]=2;
  13.         while(i<n+1){
  14.             dp[i]=dp[i-1]+dp[i-2];
  15.        i++;
  16.         }
  17.          return dp[n];
  18.     }
  19.     
  20. }

2.使用最小花费爬楼梯

  1. class Solution {
  2.     public int minCostClimbingStairs(int[] cost) {
  3.         int[] dp=new int[cost.length+1];
  4.         if(cost.length==1){
  5.             return cost[0];
  6.         }
  7.         if(cost.length==2){
  8.             return Math.min(cost[0],cost[1]);
  9.         }
  10.         
  11.         
  12.         dp[0]=cost[0];
  13.         dp[1]=cost[1];
  14.        
  15.         
  16.         int i=2;
  17.         while(i<cost.length){
  18.              dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];//dp[i],记录i之前最小的与i位置继续跳的花费。
  19.              i++;
  20.  
  21.         }
  22.         //最后一步需要考虑一下。最后两步应该跳哪个。
  23.         return Math.min(dp[cost.length-1],dp[cost.length-2]);
  24.        
  25.  
  26.     }
  27. }

3.不同路径

 

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         //设dp路径的个数。
  4.         int[][] dp=new int[m][n];
  5.         //dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条。同理。到dp[1][0],的路径也只有一条。因为不可能再改道了，是一直往下走到那的。如果换方向就到不了，因为不能往左走。
  6.         for (int i = 0; i < m; i++) dp[i][0] = 1;
  7.      for (int j = 0; j < n; j++) dp[0][j] = 1;
  8.         
  9.         for(int i=1;i<m;i++){
  10.             for(int j=1;j<n;j++){
  11.                  dp[i][j]=dp[i-1][j]+dp[i][j-1];//这俩没地方可走了。
  12.  
  13.             }
  14.         }
  15.         return dp[m-1][n-1];
  16.  
  17.     }
  18. }

4.不同路径二

  1. class Solution {
  2.     //[i][j]上如果有石头了，dp[i][j]就等于0吧。
  3.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  4.         int m=obstacleGrid.length;
  5.         int n=obstacleGrid[0].length;
  6.         int [][] dp=new int[m][n];
  7.    if(obstacleGrid[0][0]==1){
  8.        return 0;
  9.    }
  10.  
  11.  
  12.         for (int i = 0; i < m; i++){//如果横的碰到个障碍物，那剩下的都走不了了。
  13.             if(obstacleGrid[i][0]!=1){
  14.                 dp[i][0] = 1;
  15.  
  16.             }else{
  17.                 break;
  18.  
  19.             }
  20.             
  21.  
  22.  
  23.         }
  24.        for (int j = 0; j < n; j++){
  25.              if(obstacleGrid[0][j]!=1){//如果横的碰到个障碍物，从这点往后的都走不了了。
  26.                  dp[0][j] = 1;
  27.  
  28.             }else{
  29.                 break;
  30.             }
  31.  
  32.         } 
  33.  
  34.         for(int i=1;i<m;i++){
  35.             for(int j=1;j<n;j++){
  36.                 if(obstacleGrid[i][j]!=1){
  37.              dp[i][j]=dp[i-1][j]+dp[i][j-1];//如果[i][j-1]上有石头，那这个时候的路径就是只有dp[i-1][j]的。
  38.  
  39.         }
  40.  
  41.             }
  42.         }
  43.         return dp[m-1][n-1];
  44.  
  45.  
  46.     }
  47. }

5.整数拆分成两个以上的整数，让乘积最大

  1. class Solution {
  2.     //错误思路：直接开根号，然后取余直接完事。乘积最大化，肯定是从开根号那里乘。
  3.     public int integerBreak(int n) {
  4. //dp[0],dp[1]怎么设置呢？不设置d[0],d[1]，这俩没有什么意义。也不会输入0和1。
  5.       int [] dp=new int[n+1];
  6.  
  7.     dp[2]=1;
  8. //i-j，最低能到2。dp[2],拆成两项以上的，所以dp[2]=1。
  9. //同时j的上限也是i-2。保证i-j，最低是2，最低dp[2]。
  10. if(n>=3)
  11. {
  12.     for(int i=3;i<=n;i++){
  13.     for(int j=1;j<i-1;j++){
  14.           dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));//从前到后吧dp[i]，求出来，因为dp[n]，得用它推导。
  15.           //得拆成两项以上。如果直接弄成dp[i-j]*dp[j],就要拆成4项以上了。
  16.  
  17.        }
  18.  
  19. }
  20.  
  21. }
  22.      return dp[n];
  23.  
  24.     }
  25. }

6.不同的二叉搜索树。

二叉搜索树的不同，就是根的左右子树结点不同。只看结点的布局，不用看值的差异。

  1. class Solution {
  2.     public int numTrees(int n) {
  3.        // 从1到n数的先后输入顺序，也会导致建树不同。
  4.        //大佬的思路：假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，...，n为根节点，当1为根节点时，其左子树节点个数为0，右子树节点个数为n-1，同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2，所以可得G(n) = G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0)
  5.        int [] G=new int[n+1];//得用到下标G(n)
  6.        G[0]=1;
  7.        G[1]=1;
  8.        for(int i=2;i<n+1;i++){
  9.            for(int j=1;j<=i;j++){
  10.                G[i]+=G[j-1]*G[i-j];
  11.            }
  12.        }
  13.  
  14.       return G[n];
  15.  
  16.     }
  17. }

7. 0-1背包问题

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

1.设置dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2.确定递推公式，

那么可以有两个方向推出来dp[i][j]，

  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
  • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.确定初始值。

当背包剩余容量为0时，dp[i][0]=0;

当放0号物品的时候，如果d[0][j]，j的容量大于0号物品的重量。就让d[0][j]=weight[0]。

所以，如此初始化。

在java里，数组的初始值就是0。所以只需要设置d[0][j]。

  1. for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
  2.     dp[0][j] = 0;
  3. }
  4. // 正序遍历
  5. for (int j = weight[0]; j <= bagweight; j++) {
  6.     dp[0][j] = value[0];
  7. }
  1.   public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
  2.         int wlen = weight.length, value0 = 0;
  3.         //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
  4.         int[][] dp = new int[wlen + 1][bagsize + 1];
  5.         //初始化：背包容量为0时，能获得的价值都为0
  6.         for (int i = 0; i <= wlen; i++){
  7.             dp[i][0] = value0;
  8.         }
  9.         //遍历顺序：先遍历物品，再遍历背包容量
  10.         for (int i = 1; i <= wlen; i++){
  11.             for (int j = 1; j <= bagsize; j++){
  12.                 if (j < weight[i - 1]){
  13.                     dp[i][j] = dp[i - 1][j];
  14.                 }else{
  15.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
  16.                 }
  17.             }
  18.         }

一维滚动数组。

  1.  public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
  2.         int wLen = weight.length;
  3.         //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
  4.         int[] dp = new int[bagWeight + 1];
  5.         //遍历顺序：先遍历物品，再遍历背包容量
  6.         for (int i = 0; i < wLen; i++){
  7.             for (int j = bagWeight; j >= weight[i]; j--){
  8.                 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  9.             }
  10.         }

8. 0-1背包应用于分割等和子集。

把nums[i]的值，看作重量的值和value的值。

  • 背包的体积为sum / 2
  • 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
  • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。
  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         
  4.         int sum=0;
  5.         for(int num:nums){
  6.             sum+=num;
  7.         }
  8.         // 特判：如果是奇数，就不符合要求
  9.         if ((sum %2 ) != 0) {
  10.             return false;
  11.         }
  12.          int rong=sum/2;
  13.  
  14.         int[][] dp =new int [nums.length][rong+1];
  15.  
  16.         for(int j=nums[0];j<=rong;j++){
  17.             dp[0][j]=nums[0];
  18.         }
  19.         for(int i=1;i<nums.length;i++){
  20.             for(int j=0;j<=rong;j++){
  21.                 if(j<nums[i]) {
  22.                     dp[i][j]=dp[i-1][j];
  23.  
  24.                 }else{
  25.                     dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
  26.  
  27.                 }
  28.              
  29.             }
  30.         }
  31. //当走完了i，容量为rong的时候，如果里面这个值，正好是rong，也就是sum/2。说明找到了。
  32.         if(dp[nums.length-1][rong]==rong){
  33.             return true;
  34.         }else{
  35.             return false;
  36.         }
  37.  
  38.  
  39.     }
  40. }

一维的解决办法

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int sum=0;
  4.         
  5.         for(int i=0;i<nums.length;i++)
  6.         {
  7.            sum+=nums[i];
  8.         }
  9.         int target=sum/2;
  10.         double a=sum-target;
  11.         if(a!=target) return false;
  12.  
  13.         int [] dp=new int [target+1];
  14.         //背包容量为 target
  15.  
  16.         //一维背包，初始值。
  17.         dp[0]=0;
  18.  
  19.         for(int i=0;i<nums.length;i++)
  20.         {
  21.             //一维背包，j的终点 是nums[i]。
  22.             for(int j=target;j>=nums[i];j--)
  23.             {
  24.                 dp[j]=Math.max(dp[j],dp[j-nums[i]] +nums[i]);
  25.             }
  26.         }
  27.         if(dp[target]==target)
  28.         {
  29.             return true;
  30.         }else {
  31.             return false;
  32.         }
  33.         
  34.     }
  35. }

9  0-1背包用来解决最后一块石头的重量

 思路：本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

然后    结果=sum-2*dp数组最后的长度    即可。

10 用0-1背包问题，解决装成target有多少种方法。

这题的代码正好解决了这一类的问题，背就完事。

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         int sum =0;
  4.         for(int num:nums){
  5.             sum+=num;
  6.         }
  7.         //过程逆过来,留下来的数的和。留下来-减去的=target。留下来+减去的=sum。
  8.  
  9.         //所以 留下来的=(target+sum)/2。这个数必须得是整数
  10.         if((target+sum)%2==1){
  11.             return 0;
  12.         }
  13.         //如果目标值的绝对值大于sum，也没办法。
  14.         if(Math.abs(target)>sum){
  15.             return 0;
  16.         }
  17.     
  18.         //此时问题就转化为，装满容量为x背包，有几种方法。回溯肯定超时。
  19.         //dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。
  20.         int left=(target+sum)/2;
  21.         int [][] dp=new int [nums.length][left+1];
  22.  
  23.      //初始化
  24.       dp[0][0]=1;
  25.  
  26.         //只装第0个物品的目标也是给背包装满。装满了才算一种。
  27.         //dp[0][j]，看第一个元素的大小情况，进行赋值1(如果第一个元素为0.则dp[0][0]应该为2)。
  28.         for(int j=0;j<left+1;j++){
  29.             if(j==nums[0]){
  30.                 dp[0][j]+=1;
  31.             }
  32.         }
  33.        
  34.         for(int i=1;i<nums.length;i++){
  35.             //这里j从0开始。
  36.             for(int j=0;j<left+1;j++){
  37.                 //不拿/拿 第i件物品的方案数
  38.                 if(j<nums[i]){
  39.                     dp[i][j]=dp[i-1][j];
  40.                 }else{
  41.                     dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
  42.                 }
  43.                
  44.             }
  45.         }
  46.         return dp[nums.length-1][left];
  47.         
  48.  
  49.     
  50.  
  51.  
  52.  
  53.  
  54.     }
  55. }

一维数组的

  1. class Solution {
  2.     public int findTargetSumWays(int[] nums, int target) {
  3.         int sum = 0;
  4.         for (int i = 0; i < nums.length; i++) sum += nums[i];
  5.         if ((target + sum) % 2 != 0) return 0;
  6.         int size = (target + sum) / 2;
  7.         if(size < 0) size = -size;
  8.         int[] dp = new int[size + 1];
  9.         dp[0] = 1;
  10.         for (int i = 0; i < nums.length; i++) {
  11.             for (int j = size; j >= nums[i]; j--) {
  12.                 dp[j] += dp[j - nums[i]];
  13.             }
  14.         }
  15.         return dp[size];
  16.     }
  17. }

11.0-1背包的二维背包。(记得这样做，就行，不用管过程）

记得这些代码有什么作用就行，不用管每一步怎么来的。

题目简要说明：找到的字符串，里面都会有0.1，

让找的字符串集合里最多有m个0，n个1。这个字符串集合尽量要大。

 而m 和 n相当于是一个背包，两个维度的背包

  1. class Solution {
  2.     public int findMaxForm(String[] strs, int m, int n) {
  3.         int len =strs.length;
  4.         int [][]  nums = new int [len][2];
  5.         //首先遍历一遍，把每个字符串0和1的数量存进新数组，然后用双重背包即可。
  6.         for(int i=0;i<strs.length;i++)
  7.         {
  8.             int a=finZero(strs[i]);
  9.             int b=findOne(strs[i]);
  10.             nums[i][0]=a;
  11.             nums[i][1]=b;
  12.         }
  13.         int [][] dp =new int [m+1][n+1];
  14.         for(int i=0;i<len;i++)
  15.         {
  16.             for(int j=m;j>=nums[i][0];j--)
  17.             {
  18.                 for(int k=n;k>=nums[i][1];k--)
  19.                 {
  20.                     //这个递推公式是求个数，所以是+1
  21.                  dp[j][k]=Math.max(dp[j][k],dp[j-nums[i][0]][k-nums[i][1]]+1);
  22.                 }
  23.             }
  24.         }
  25.         return  dp[m][n];
  26.     }
  27.  
  28.     //这两个函数，发现每个字符串的0，1数量
  29.     int findOne(String s)
  30.     {
  31.         int cnt=0;
  32.         for(int i=0;i<s.length();i++)
  33.         {
  34.             if(s.charAt(i)=='1')   cnt++;  
  35.         }
  36.         return cnt;
  37.     }
  38.     int finZero(String s)
  39.     {
  40.         int cnt=0;
  41.         for(int i=0;i<s.length();i++)
  42.         {
  43.              if(s.charAt(i)=='0')   cnt++;
  44.         }
  45.         return cnt;
  46.     }
  47.  
  48. }

12.完全背包问题。

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

  1. //先遍历物品，再遍历背包
  2. private static void testCompletePack(){
  3.     int[] weight = {1, 3, 4};
  4.     int[] value = {15, 20, 30};
  5.     int bagWeight = 4;
  6.     int[] dp = new int[bagWeight + 1];
  7.     for (int i = 0; i < weight.length; i++){ // 遍历物品
  8.         for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
  9.             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  10.         }
  11.     }
  12.     for (int maxValue : dp){
  13.         System.out.println(maxValue + "   ");
  14.     }
  15. }
  16.  
  17. //先遍历背包，再遍历物品
  18. private static void testCompletePackAnotherWay(){
  19.     int[] weight = {1, 3, 4};
  20.     int[] value = {15, 20, 30};
  21.     int bagWeight = 4;
  22.     int[] dp = new int[bagWeight + 1];
  23.     for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
  24.         for (int j = 0; j < weight.length; j++){ // 遍历物品
  25.             if (i - weight[j] >= 0){
  26.                 dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
  27.             }
  28.         }
  29.     }
  30.     for (int maxValue : dp){
  31.         System.out.println(maxValue + "   ");
  32.     }
  33. }

13.（零钱兑换）完全背包问题，装到target有多少种？

一维数组的。太啥比，就是把本章第10题的，内层for的遍历顺序调反即可。

  1. class Solution {
  2.     public int change(int amount, int[] nums) {
  3.         int [] dp=new int [amount+1];
  4.          dp[0] = 1;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             for (int j = nums[i]; j <amount+1; j++) {
  7.                 dp[j] += dp[j - nums[i]];
  8.             }
  9.         }
  10.         return dp[amount];
  11.         
  12.  
  13.     }
  14. }

14.组合综合IV（外层遍历背包）

组合不强调顺序，(1,5)和(5,1)是同一个组合。

排列强调顺序，(1,5)和(5,1)是两个不同的排列。

看题目，本题其本质是本题求的是排列总和，而且仅仅是求排列总和的个数

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

 此时当外层for遍历背包时，得让j从0开始。

  1. class Solution {
  2.     public int combinationSum4(int[] nums, int target) {
  3.         int[] dp=new int[target+1];
  4.         dp[0]=1;
  5.         for(int i=0;i<target+1;i++){
  6.             for(int j=0;j<nums.length;j++){
  7.                 if(i>=nums[j])//外层遍历容量时，里面容量i必须大于nums[j]
  8.                 dp[i]+=dp[i-nums[j]];//此时外层遍历背包容量时，写成这样
  9.             }
  10.         }
  11.         return dp[target];
  12.  
  13.     }
  14. }

15.爬楼梯（外层遍历背包）

比如上4楼，112和221是两种排列。用完全背包。

16.零钱兑换(求零钱组成target的最少硬币数）（求最少的target典范）

这题可以看出，当dp求最多时，除了dp[0]，都会初始化成0，来递推比较，在递推公式那里用max函数比较。

当dp求最少的时候，除了除了dp[0]，都会初始化成int的MAX_VALUE,在递推公式那里用min函数比较。

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int[] dp=new int[amount+1];//最少需要的硬币数
  4.         
  5.         int max=Integer.MAX_VALUE;
  6.         //初始化dp数组为最大值
  7.         for (int j = 0; j < dp.length; j++) {
  8.             dp[j] = max;
  9.         }
  10.         dp[0]=0;
  11.         for(int i=0;i<coins.length;i++){
  12.             for(int j=coins[i];j<amount+1;j++){
  13.                 if(dp[j-coins[i]]!=max){
  14.                      //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
  15.                     dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
  16.  
  17.                 }
  18.                 
  19.             }
  20.  
  21.         }
  22.         //如果没有通往前面的道路，那dp[amount]的值不会到dp[0],而是保持初始值
  23.         if(dp[amount]==max){
  24.             return -1;
  25.         }else{
  26.             return dp[amount];
  27.  
  28.         }
  29.  
  30.  
  31.     }
  32. }

17.16题的变种，可变的nums[i]数组，我们在循环中构建它

  1. class Solution {
  2.     //我们拿的数得是平方的数。
  3.     public int numSquares(int n) {
  4.         int[] dp=new int[n+1];
  5.         
  6.         int max=Integer.MAX_VALUE;
  7.         //初始化dp数组为最大值
  8.         for (int j = 0; j < dp.length; j++) {
  9.             dp[j] = max;
  10.         }
  11.         dp[0]=0;
  12.         //这里的难点就是把nums[i]，转化为i*i
  13.         for(int i=0;i*i<=n;i++){
  14.             for(int j=i*i;j<=n;j++){
  15.                 if(dp[j-i*i]!=max){
  16.                      //只有dp[j-i*i]不是初始最大值时，该位才有选择的必要
  17.                     dp[j]=Math.min(dp[j],dp[j-i*i]+1);
  18.  
  19.                 }
  20.                 
  21.             }
  22.  
  23.         }
  24.         return dp[n];
  25.  
  26.     }
  27. }

18.单词拆分，用字典里所给的字符串    拼出所需要的字符串S

此题类似于分割回文串。

思路：挨个判断，S里的字符串是不是在字典里都出现过。

在for里创造一个[j,i)的子串区间，判断这个子串是否在字典里出现过。

  1. class Solution {
  2.     //思路：挨个判断，S里的字符串是不是在字典里都出现过。
  3.     public boolean wordBreak(String s, List<String> wordDict) {
  4.         boolean [] dp=new boolean[s.length()+1];
  5.         //默认为false了。因此你要把true往后传递呀
  6.         dp[0]=true;
  7.         //得用sbstring方法，i肯定在右侧，i-1得>=0,所以让i从1开始，j从0开始,
  8.         for(int i=1;i<=s.length();i++){
  9.             //做右界，所以范围为1-
  10.             for(int j=0;j<i;j++){
  11.                 //之前访问到j这里也得是true，必须得所有的单词都在字典里
  12.                 if(wordDict.contains(s.substring(j,i))&&dp[j]==true){
  13.                     dp[i]=true;
  14.                 }
  15.             }
  16.         }
  17.         return dp[s.length()];
  18.  
  19.  
  20.     }
  21. }

19.多重背包问题

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

比如说这种题是多重背包。

我们可以把它摊开 ，转化成了01背包的问题。

重新建一个数组，将3维变成二维。

  1. public void testMultiPack1(){
  2.     // 版本一：改变物品数量为01背包格式
  3.     List<Integer> weight = new ArrayList<>(Arrays.asList(1, 3, 4));
  4.     List<Integer> value = new ArrayList<>(Arrays.asList(15, 20, 30));
  5.     List<Integer> nums = new ArrayList<>(Arrays.asList(2, 3, 2));
  6.     int bagWeight = 10;
  7.  
  8.     for (int i = 0; i < nums.size(); i++) {
  9.         while (nums.get(i) > 1) { // 把物品展开为i
  10.             weight.add(weight.get(i));
  11.             value.add(value.get(i));
  12.             nums.set(i, nums.get(i) - 1);
  13.         }
  14.     }
  15.  
  16.     int[] dp = new int[bagWeight + 1];
  17.     for(int i = 0; i < weight.size(); i++) { // 遍历物品
  18.         for(int j = bagWeight; j >= weight.get(i); j--) { // 遍历背包容量
  19.             dp[j] = Math.max(dp[j], dp[j - weight.get(i)] + value.get(i));
  20.         }
  21.         System.out.println(Arrays.toString(dp));
  22.     }
  23. }

20.打家劫舍

题目描述：每家都有钱，不能连续偷两家。

分析：

1.如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

2.如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]

，选好出发点。

从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

这里没有背包，不是背包的题，所以只需要遍历数组即可。

  1. // 动态规划
  2. class Solution {
  3. 	public int rob(int[] nums) {
  4. 		if (nums == null || nums.length == 0) return 0;
  5. 		if (nums.length == 1) return nums[0];
  6.  
  7. 		int[] dp = new int[nums.length];
  8. 		dp[0] = nums[0];
  9. 		dp[1] = Math.max(dp[0], nums[1]);
  10. 		for (int i = 2; i < nums.length; i++) {
  11. 			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  12. 		}
  13.  
  14. 		return dp[nums.length - 1];
  15. 	}
  16. }

21.打家劫舍||

题目表述：要偷的房子围成了一圈，首位相邻，不能偷相邻的屋子。

这题还是得动态规划，不能省事只算不相邻。

成环的情况可以分为三种处理。

  • 情况一：考虑不包含首尾元素

  • 情况二：考虑包含首元素，不包含尾元素

  • 情况三：考虑包含尾元素，不包含首元素

 成环问题：情况二，三包括情况1。

所以我们按照下标建两个数组，比较它们的结果即可。

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.  
  4.       if (nums == null || nums.length == 0)
  5.             return 0;
  6.  
  7.         int len = nums.length;
  8.         if (len == 1)
  9.             return nums[0];
  10.         return Math.max(work(nums, 0, len-2), work(nums, 1, len-1));
  11.      
  12.     }
  13.      int work(int[] p,int start,int end){
  14.  
  15.         if(start==end){
  16.             return p[start];
  17.         }
  18.         if(end-start==1){
  19.             return Math.max(p[start],p[end]);
  20.         }
  21.  
  22.         int[] nums=new int[end-start+1];
  23.         int index=0;
  24.         for(int i=start;i<=end;i++){
  25.             nums[index]=p[i];
  26.             index++;
  27.         }
  28.  
  29.  
  30.         //新建一个数组nums。此时就可以看成，可以忽略首尾相连的了。
  31.        
  32.         int[] dp=new int[nums.length];
  33.         dp[0]=nums[0];
  34.         dp[1]=Math.max(nums[0],nums[1]);
  35.         for(int i=2;i<nums.length;i++){
  36.             dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
  37.         }
  38.         return dp[nums.length-1];
  39.         
  40.        
  41.     }
  42. }

22.打家劫舍|||(树形动态规划）

经过仔细分析（手动严肃脸），正确的解题思路大致是这样的：

  • 对于一个以 node 为根节点的二叉树而言，如果尝试偷取 node 节点，那么势必不能偷取其左右子节点，然后继续尝试偷取其左右子节点的左右子节点。

  • 如果不偷取该节点，那么只能尝试偷取其左右子节点。

  • 比较两种方式的结果，谁大取谁。

暴力递归

  1. class Solution {
  2.     // 1.递归去偷，超时
  3.     public int rob(TreeNode root) {
  4.         if (root == null)
  5.             return 0;
  6.         int money = root.val;
  7.         if (root.left != null) {
  8.             money += rob(root.left.left) + rob(root.left.right);
  9.         }
  10.         if (root.right != null) {
  11.             money += rob(root.right.left) + rob(root.right.right);
  12.         }
  13.         return Math.max(money, rob(root.left) + rob(root.right));
  14.     }
  15. }

我们计算了root的四个孙子（左右孩子的孩子）为头结点的子树的情况，又计算了root的左右孩子为头结点的子树的情况(return 那里又计算了）。

所以计算左右孩子的时候其实又把孙子计算了一遍。复杂度为n的平方。

所以我们剪枝，如果这个值已经被计算过了，那就直接拿来用，不用再重新计算。

  1. //后序遍历,用儿子的与父亲比较，如果父亲的大，则拿父亲的钱，则下一步去找父亲的孙子。
  2. class Solution {
  3.     Map<TreeNode,Integer> map=new HashMap<>();
  4.  
  5.     public int rob(TreeNode root) {
  6.         if(root==null){
  7.             return 0;
  8.         }
  9.         if(map.containsKey(root)){
  10.             return map.get(root);
  11.         }
  12.         int money=root.val;
  13.         if(root.left!=null){
  14.             money+=rob(root.left.left)+rob(root.left.right);
  15.         }
  16.          if(root.right!=null){
  17.             money+=rob(root.right.left)+rob(root.right.right);
  18.         }
  19.         
  20.          int res=Math.max(money,rob(root.left)+rob(root.right));
  21.          map.put(root,res);
  22.         return res;
  23.  
  24.     }
  25.  
  26.  
  27. }

23.买卖股票的最佳时机一

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1.贪心算法的做法

  1. class Solution {
  2.     //选左侧最小值，然后一边遍往右走，用右侧最大值减去最小值。
  3.     public int maxProfit(int[] prices) {
  4.         int low=Integer.MAX_VALUE;
  5.         int res=0;
  6.         for(int i=0;i<prices.length;i++){
  7.             low=Math.min(prices[i],low);
  8.             res=Math.max(prices[i]-low,res);
  9.         }
  10.         return res;
  11.          
  12.  
  13.     }
  14. }

2.动态规划的做法

思路：确定dp，dp[i][0] 表示第i天持有股票所得最多现金，持有的概念就是自己还有股在身上。

                          dp[i][1] 表示第i天不持有股票所得最多现金，自己手里没有股票。

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]。只在今天这一天出手

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

  • 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  • 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

所以我们得初始化俩值。dp[0][0]和dp[0][1],

那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] =  -prices[0];

dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;

确定遍历顺序

从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。

  1. class Solution {
  2.   
  3.     public int maxProfit(int[] prices) {
  4.         int [][] dp=new int[prices.length][2];
  5.         dp[0][0]=-prices[0];
  6.         dp[0][1]=0;
  7.         for(int i=1;i<prices.length;i++){
  8.             dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
  9.             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
  10.         }
  11.         return dp[prices.length-1][1];
  12.        
  13.  
  14.     }
  15. }

24.买卖股票的最佳时机二

在这一周里可以你可以尽可能地完成更多的交易（多次买卖一支股票）。一个星期可以交易好几次，与上一题不同，上一次只能买一次。

这里重申一下dp数组的含义：

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]

买新的时候，必须得之前不持有。在第i天持有时，还可能有之前赚的钱在。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.             int [][] dp=new int[prices.length][2];
  4.         dp[0][0]=-prices[0];
  5.         dp[0][1]=0;
  6.         for(int i=1;i<prices.length;i++){
  7.             //与第一题不同，这里改了
  8.             dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
  9.             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
  10.         }
  11.         return dp[prices.length-1][1];
  12.  
  13.     }
  14. }

25.买卖股票的最佳时机III

这次给了局限，你最多只能完成两次交易。 

1.确定dp数组有以下几种状态。

  

        0没有操作（没有持有）

        1第一次买入（第一次持有）

        2第一次卖出（第一次不持有）

        3第二次买入 （第二次持有）

       4第二次卖出   （第二次不持有）

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票（即第一次持有）

2.达到dp[i][1]状态，有两个具体操作：

  • 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
  • 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
  • dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

  • 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
  • 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])。

所以

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

3.确定初始值。

dp[0][0] = 0;第0天也没操作。

dp[0][1] = -prices[0];

dp[0][2]=0;//今天买今天卖。

dp[0][3]=-prices[0];//又买一遍。

dp[0][4]==0;

4.确定遍历顺序

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int[][] dp=new int[prices.length][5];
  4.         dp[0][0]=0;
  5.         dp[0][1]=-prices[0];
  6.         dp[0][2]=0;
  7.         dp[0][3]=-prices[0];
  8.         dp[0][4]=0;
  9.  
  10.         for(int i=1;i<prices.length;i++){
  11.             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
  12.             dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
  13.             dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
  14.             dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
  15.       
  16.         }
  17.         return dp[prices.length-1][4];
  18.  
  19.     }
  20. }

26.买卖股票的最佳时机四

上一题的两笔改成k笔。

  1. class Solution {
  2.     public int maxProfit(int k, int[] prices) {
  3.         if (prices.length == 0) return 0;
  4.         int[][] dp=new int[prices.length][2*k+1];
  5.         //初始化数组。
  6.         for(int i=0;i<=2*k;i++){
  7.             if(i%2==0){
  8.                 dp[0][i]=0;
  9.  
  10.             }else{
  11.                dp[0][i]=-prices[0];
  12.             } 
  13.         }
  14.         for(int i=1;i<prices.length;i++){
  15.             //改造了一下，只能交易二次的那一题
  16.             for(int j=1;j<=2*k;j++){
  17.                 if(j%2==1){
  18.                     dp[i][j]=Math.max( dp[i - 1][j],dp[i-1][j-1] - prices[i]);
  19.                 }else{
  20.                     dp[i][j]=Math.max( dp[i - 1][j],dp[i-1][j-1] +prices[i]);
  21.                 }
  22.                
  23.             }
  24.             
  25.         }
  26.         return dp[prices.length-1][2*k];
  27.  
  28.     }
  29. }

27.最佳买卖股票时机含冷冻期（复杂）

之前多次买卖同一只股票，这里如果今天卖了，那么明天不能买，得隔一天才能买。这次的买入，距离上次的卖出，得中间隔着一天。

思路：分为四种状态。

  • 状态一：持有股票状态，今天买入股票，或者是之前就买入了股票然后没有操作
  • 卖出股票状态，这里就有两种卖出股票状态
    • 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
    • 状态三：今天卖出了股票.
  • 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

达到持有股票状态（状态一）即：dp[i][0]，有两个具体操作：

  • 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
  • 操作二：今天买入了，有两种情况
    • 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
    • 前一天已经卖了，保持卖出状态（状态二）再买入，dp[i - 1][1] - prices[i]
    • 所以操作二取最大值，即：max(dp[i - 1][3], dp[i - 1][1]) - prices[i]

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

  • 操作一：前一天就是状态二（即已经卖出）
  • 操作二：前一天是冷冻期（状态四），延续这个卖出状态。

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

  • 操作一：昨天一定是持有股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

  • 操作一：昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

综上所述

  1. dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
  2. dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
  3. dp[i][2] = dp[i - 1][0] + prices[i];
  4. dp[i][3] = dp[i - 1][2];

这里主要讨论一下第0天如何初始化。

如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，买入股票所剩现金为负数。

保持卖出股票状态（状态二），第0天没有卖出dp[0][1]初始化为0就行，

今天卖出了股票（状态三），同样dp[0][2]初始化为0，因为最少收益就是0，绝不会是负数。

同理dp[0][3]也初始为0。

最后结果是取 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int[][] dp=new int [prices.length][4];
  4.         dp[0][0]=-prices[0];
  5.         dp[0][1]=0;
  6.         dp[0][2]=0;
  7.         dp[0][3]=0;
  8.         for(int i=1;i<prices.length;i++){
  9.             dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
  10.             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
  11.             dp[i][2] = dp[i - 1][0] + prices[i];
  12.             dp[i][3] = dp[i - 1][2];
  13.         }
  14.         //最后结果是取 状态二，状态三，和状态四的最大值，是冷冻期也可能是最大值。
  15.        return Math.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));
  16.  
  17.  
  18.     }
  19. }

28.买卖股票的最佳时机(含手续费)多次买一支，但有手续费。

  1. class Solution {
  2.     public int maxProfit(int[] prices, int fee) {
  3.  
  4.         int [][] dp=new int[prices.length][2];
  5.         dp[0][0]=-prices[0];
  6.         dp[0][1]=0;//表示第1天不持有股票所得最多现金
  7.         for(int i=1;i<prices.length;i++){
  8.             //的区别就是这里需要多一个减去手续费的操作。
  9.             dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
  10.             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
  11.         }
  12.         return dp[prices.length-1][1];
  13.  
  14.     }
  15. }

30.最长递增子序列(没看懂）

 我没用动态规划的方法做，错了。这题应该用动态规划。

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度.

位置  i   的最长升序子序列   等于   j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

dp[i]，所有的位置上初始值都为1。因为包括它们自身。

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         if(nums==null||nums.length==0){
  4.             return 0;
  5.         }
  6.         if(nums.length==1){
  7.             return 1;
  8.         }
  9.         int[] dp=new int[nums.length];
  10.         Arrays.fill(dp,1);
  11.  
  12.         for(int i=1;i<nums.length;i++){
  13.             for(int j=0;j<=i-1;j++){
  14.                 //我现在在位置i，如果我比这之前的有个数要大，那么长度就为这个数的最长+1。
  15.                 if(nums[i]>nums[j]){
  16.                     dp[i]=Math.max(dp[i],dp[j]+1);
  17.                }
  18.             }
  19.  
  20.  
  21.         }
  22.          //最后一位，并不一定是最大长度
  23.        int res=0;
  24.        for(int i=0;i<dp.length;i++){
  25.            res=Math.max(dp[i],res);
  26.        }
  27.        return res;
  28.       
  29.     }
  30. }

31.最长连续递增序列

没用动态规划，因为太简单了。

  1. class Solution {
  2.     public int findLengthOfLCIS(int[] nums) {
  3.         if(nums==null||nums.length==0){
  4.             return 0;
  5.         }
  6.         if(nums.length==1){
  7.             return 1;
  8.         }
  9.  
  10.         int pre=0;
  11.         int maxLength=1;
  12.         //记录一下最长连续增加即可。用pre表示左区间。
  13.         for(int i=0;i<nums.length-1;i++){
  14.             if(nums[i+1]>nums[i]){
  15.                 maxLength=Math.max(maxLength,i+1-pre+1);
  16.             }else{
  17.                 pre=i+1;
  18.             }
  19.  
  20.         }
  21.         return maxLength;
  22.  
  23.     }
  24. }
  25.  
  26.  
  27.

32.最长重复子数组(用我的思路，别看代码随想录）

我用双指针的暴力破解方法失败！

dp[i][j] ：以下标i 为结尾的A，和以下标j 为结尾的B，最长重复子数组长度为dp[i][j]。

根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。

即当A[i ] 和B[j ]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;

所以 i和j都要从1开始遍历。

初始化dp[i][0]与dp[0][j]，因为dp[i][j]从这里推导出来。如果碰到相等的，让它们为1即可。

  1.  for(int j=0;j<nums2.length;j++ ){
  2.             if(nums1[0]==nums2[j]){
  3.                 dp[0][j]=1;
  4.                 res=1;
  5.             }
  6.         }
  7.         for(int j=0;j<nums1.length;j++ ){
  8.             if(nums1[j]==nums2[0]){
  9.                 dp[j][0]=1;
  10.                 res=1;
  11.             }
  12.         }

所以dp[i][0] 和dp[0][j]初始化为0。

并不是dp[i][j]里的i和j都取最大值时，才有最长重复子数组。dp[i][j]那里可能是0。

所以在这个过程需要一个res来记录。

完整代码如下

  1. class Solution {
  2.     public int findLength(int[] nums1, int[] nums2) {
  3.  
  4.         int[][] dp=new int[nums1.length+1][nums2.length+1];
  5.         int res=0;
  6.         //因为 dp[i][j]=dp[i-1][j-1]+1;，i和j必须从1开始，
  7.         for(int j=0;j<nums2.length;j++ ){
  8.             if(nums1[0]==nums2[j]){
  9.                 dp[0][j]=1;
  10.                 res=1;
  11.             }
  12.         }
  13.         for(int j=0;j<nums1.length;j++ ){
  14.             if(nums1[j]==nums2[0]){
  15.                 dp[j][0]=1;
  16.                 res=1;
  17.             }
  18.         }
  19.         for(int i=1;i<nums1.length;i++){
  20.             for(int j=1;j<nums2.length;j++){
  21.                 if(nums1[i]==nums2[j]){
  22.                     dp[i][j]=dp[i-1][j-1]+1;
  23.                     res=Math.max(res,dp[i][j]);
  24.                 }
  25.             }
  26.         }
  27.         return res;
  28.  
  29.        
  30. }
  31. }

不用两个for来定义初始值的版本，多给了一个长度。

  1. class Solution {
  2.     public int findLength(int[] nums1, int[] nums2) {
  3.         int result = 0;
  4.         int[][] dp = new int[nums1.length + 1][nums2.length + 1];
  5.         
  6.         for (int i = 1; i < nums1.length + 1; i++) {
  7.             for (int j = 1; j < nums2.length + 1; j++) {
  8.                 if (nums1[i - 1] == nums2[j - 1]) {
  9.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  10.                     result = Math.max(result, dp[i][j]);
  11.                 }
  12.             }
  13.         }
  14.         
  15.         return result;
  16.     }
  17. }

33.最长公共子序列

与最长重复子数组的区别是，里面的元素重复时，可以不是连续的。

处理两种情况，当这俩不相等时，你得取

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  1. class Solution {
  2.     public int longestCommonSubsequence(String text1, String text2) {
  3.         int[][] dp=new int[text1.length()+1][text2.length()+1];
  4.         //dp[i][j] ： S1的0到i-1，S2的0到j-1    最长公共子序列长度。
  5.      
  6.         int res=0;
  7.          for(int i=1;i<=text1.length();i++){
  8.              for(int j=1;j<=text2.length();j++){
  9.                  if(text1.charAt(i-1)==text2.charAt(j-1)){
  10.                      dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
  11.                      res=Math.max(res,dp[i][j]);
  12.  
  13.                  }else{
  14.                      dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
  15.                      res=Math.max(res,dp[i][j]);
  16.                  }
  17.  
  18.              }
  19.             
  20.          }
  21.        return res;
  22.  
  23.     }
  24. }

34.不相交的线

这题与最长公共子序列一摸一样。

  1. class Solution {
  2.   public int maxUncrossedLines(int[] A, int[] B) {
  3.   	int [][] dp = new int[A.length+1][B.length+1];
  4.       int res=0;
  5.   	for(int i=1;i<=A.length;i++) {
  6.   		for(int j=1;j<=B.length;j++) {
  7.   			if (A[i-1]==B[j-1]) {
  8.   				dp[i][j]=dp[i-1][j-1]+1;
  9.                   res=Math.max(dp[i][j],res);
  10.   			}
  11.   			else {
  12.   				dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
  13.   			}
  14.   		}
  15.   	}
  16.       //也可以返回dp[A.length][B.length];因为与最长公共子序列那题不同的是，它只走一遍。
  17.   	return res;
  18.   }
  19. }

35.最大子数组之和（连续的）

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         if(nums.length==1){
  4.             return nums[0];
  5.         }
  6.             int [] dp=new int[nums.length];
  7.             int res=nums[0];
  8.             dp[0]=nums[0];
  9.         //当dp[i]小于0了，就让它从下一个整数开始。
  10.             for(int i=1;i<nums.length;i++){
  11.                 dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);    
  12.                 res=Math.max(res,dp[i]);   
  13.             }
  14.            
  15.             return res;
  16.  
  17.     }
  18. }

36.判断子序列

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

如果考察的是连续子序列，用KMP算法。

用动态规划吧。最长公共子序列那一套。如果最长公共子序列长度一样，则是。

  1. class Solution {
  2.     public boolean isSubsequence(String s, String t) {
  3.         int[][] dp=new int[s.length()+1][t.length()+1];
  4.         //dp[i][j] ： S1的0到i-1，S2的0到j-1    最长公共子序列长度。
  5.      
  6.         int res=0;
  7.          for(int i=1;i<=s.length();i++){
  8.              for(int j=1;j<=t.length();j++){
  9.                  if(s.charAt(i-1)==t.charAt(j-1)){
  10.                      dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
  11.                      res=Math.max(res,dp[i][j]);
  12.  
  13.                  }else{
  14.                      dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
  15.                      res=Math.max(res,dp[i][j]);
  16.                  }
  17.  
  18.              }
  19.             
  20.          }
  21.        return (res==s.length());
  22.     }
  23.        
  24. }

37.不同的子序列（完全不会）

 错误思路：用最长公共子序列的方法，当dp里长度==子序列的时候+1。

  1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

2.这一类问题，基本是要分析两种情况

  • s[i - 1] 与 t[j - 1]相等
  • s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。

一部分是不用s[i - 1]来匹配（看作s[i - 1] 与 t[j - 1]不相等），个数为dp[i - 1][j]。因为t是s的子串

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

当s[i - 1] 与 t[j - 1]不相等时（真正的不相等），dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]

因为已知t只能是s的子串，在前面最长公共子序列里取的是max(dp[i][j-1],dp[i-1][j]);因为不知道谁是谁的子串。

3.初始值怎么设置？

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j];

当i等于0时，有dp[0][j],当j等0时，有dp[i-1][0]

中可以看出dp[i][0] 和dp[0][j]是一定要初始化的。

dp[0][j]肯定为0。此时S的  0减去1=-1  之前，t肯定匹配不上。

dp[i][0]。此时t之前的 下标为-1的串，匹配结果只有 1个。所以定为1。

  1. class Solution {
  2.  
  3.     public int numDistinct(String s, String t) {
  4.         //dp[i][j]：以i-1为结尾的s的子序列   中  出现以j-1为结尾的t的子序列的个数为dp[i][j]。
  5.         int[][] dp=new int[s.length()+1][t.length()+1];
  6.         //dp[0][j]肯定为0。此时S的  0减去1=-1  之前，t肯定匹配不上。
  7.         //dp[i][0]。此时t之前的 下标为-1的串，匹配结果只有 1个。所以定为1。
  8.         for(int i=0;i<s.length();i++){
  9.             dp[i][0]=1;
  10.         }
  11.         for(int i=1;i<=s.length();i++){
  12.             for(int j=1;j<=t.length();j++){
  13.                  if(s.charAt(i-1)==t.charAt(j-1)){
  14.                      //左面加的是当作匹配上，右边加的是当作匹配不上
  15.                      dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
  16.  
  17.                  }else{
  18.                      //确实匹配不上时
  19.                      dp[i][j]=dp[i-1][j];
  20.                  }
  21.  
  22.              }
  23.         }
  24.         //这个时候递推肯定最大
  25.         return dp[s.length()][t.length()];
  26.  
  27.     }
  28. }

38.两个字符串的删除操作

  1. class Solution {
  2.     //找到最长公共子序列的长度，然后分别去除两个字符串中除了最长公共子序列的字符数。
  3.     public int minDistance(String S1, String S2) {
  4.         int[][] dp=new int[S1.length()+1][S2.length()+1];
  5.         int res=0;
  6.         for(int i=1;i<=S1.length();i++){
  7.             for(int j=1;j<=S2.length();j++){
  8.                 if(S1.charAt(i-1)==S2.charAt(j-1)){
  9.                     dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);
  10.                     res=Math.max(res,dp[i][j]);
  11.                 }else{
  12.                     dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
  13.                 }
  14.             }
  15.         }
  16.         return S1.length()+S2.length()-2*res;
  17.  
  18.  
  19.     }
  20. }

39.编辑距离(不能使用最长公共子序列，部分测试用例无法通过）

1.dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

2.确定递推公式

  1. if (word1[i - 1] == word2[j - 1])
  2.     不操作
  3. if (word1[i - 1] != word2[j - 1])
  4.     增
  5.     删
  6.     换

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

  • 操作一删除元素：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。即  dp[i][j] = dp[i - 1][j] + 1;
  • 操作二增加元素：不相等时，word增了一个，意味着此时指针指向的word1与word2的值相等，所以我们应该删掉word2的这一项。word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。即 dp[i][j] = dp[i][j - 1] + 1;

  • 操作三替换元素：，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。     即 dp[i][j] = dp[i - 1][j - 1] + 1;//换成一样的了。

3.初始化问题，dp[i][0] 和 dp[0][j]肯定得用到。

那么dp[i][0] 和 dp[0][j] 表示什么呢？

dp[i][0]应该表示word1的子序列   0到i-1    全删光，共i个操作步骤。

dp[0][j]应该表示word1从头增加到word2子序列   0到j-1的长度，共j个步骤。

dp[0][0]=0;这俩都是空了都不用动手。

  1. class Solution {
  2.     //将word1转换成word2所用最少操作数。
  3.     public int minDistance(String S1, String S2) {
  4.        
  5.  
  6.         //dp表示 S1的 0到i-1子串，与S2的0到j-1的子串的最短编辑距离。
  7.         int[][] dp=new int[S1.length()+1][S2.length()+1];
  8.         for(int i=0;i<=S1.length();i++){
  9.             dp[i][0]=i;
  10.         }
  11.          for(int j=0;j<=S2.length();j++){
  12.             dp[0][j]=j;
  13.         }
  14.  
  15.         for(int i=1;i<=S1.length();i++){
  16.             for(int j=1;j<=S2.length();j++){
  17.                 if(S1.charAt(i-1)==S2.charAt(j-1)){
  18.                     dp[i][j]=dp[i-1][j-1];
  19.                    
  20.                 }else{
  21.                     //求的是最小编辑距离
  22.                     dp[i][j]= Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
  23.                 }
  24.             }
  25.         }
  26.         return dp[S1.length()][S2.length()];
  27.        
  28.     
  29.         
  30.  
  31.     }
  32. }
  33.  
  34.

40.回文子串

动态规划做法

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，dp[i][j]一定是false。

当s[i]与s[j]相等时，有如下三种情况

  • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
  • 情况二：下标i 与 j相差为1，例如aa，也是回文子串
  • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

dp[i + 1][j - 1],所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

  1. class Solution {
  2.     public int countSubstrings(String s) {
  3.         //dp[i][j]表示i和j这个区间的是回文子串。
  4.         boolean [][] dp=new boolean[s.length()][s.length()];
  5.        int count=0;
  6.        for(int i=s.length()-1;i>=0;i--){
  7.            //j得大于等于i
  8.             for(int j=i;j<s.length();j++){
  9.                   if(s.charAt(i)==s.charAt(j)){
  10.                       //当a和aa时，直接可以设置位true。
  11.                       if(j-i<=1){
  12.                      dp[i][j]=true;
  13.                       count++;
  14.                       }else{
  15.                           //j-i>1时，如果它的子是回文，且此时已有s[i]==s[j]，则计数加一。
  16.                           if(dp[i+1][j-1]){
  17.                               dp[i][j]=true;
  18.                             count++;
  19.  
  20.                           }
  21.                       }         
  22.             }
  23.         }   
  24.     }
  25.     return count;
  26. }
  27. }

双指针做法：中心扩散法

首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。

在遍历中心点的时候，要注意中心点有两种情况。

一个元素可以作为中心点，两个元素也可以作为中心点。

每个中心点标识一个字符串S。

  1. class Solution {
  2.     public int countSubstrings(String s) {
  3.         int result=0;
  4.         for(int i=0;i<s.length();i++){
  5.             result+=work(s,i,i);
  6.             result+=work(s,i,i+1);
  7.         }
  8.  
  9.         
  10.     return result;
  11.    }
  12.        int work(String S,int index,int index2){
  13.            int count=0;
  14.            //尽量把判断写在一起。不然可能会超时
  15.            while(index2<S.length()&&index>=0&&S.charAt(index)==S.charAt(index2)){
  16.                count++;
  17.                index--;
  18.                index2++;
  19.            }
  20.              return count;
  21.            
  22.  
  23.  
  24.     }
  25. }

41.最长回文子序列（回文想到reverse）

序列的区别就是可以不连续。

方法一：动态规划复杂

 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

dp数组如何初始化

首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和 j 相同时候的情况。

所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

  1. class Solution {
  2.     public int longestPalindromeSubseq(String s) {
  3.         int [][] dp=new int [s.length()+1][s.length()+1];
  4.         //i到j之间的最长回文子序列。
  5.  
  6.         // dp[i][j]=dp[i+1][j-1]+2;
  7.         for(int i=s.length()-1;i>=0;i--){
  8.             dp[i][i]=1;//我们只看两位的。
  9.             for(int j=i+1;j<s.length();j++){
  10.                 if(s.charAt(i)==s.charAt(j)){
  11.                     dp[i][j]=dp[i+1][j-1]+2;
  12.                 }else{
  13.                     dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
  14.                 }
  15.             }
  16.         }
  17.         //返回的区间应该位0-s.length()-1
  18.         return dp[0][s.length()-1];
  19.  
  20.     }
  21. }

方法二：s与s.reverse()的最长公共子序列即为其最长回文子序列

  1. class Solution {
  2.     public int longestPalindromeSubseq(String text1) {
  3.         
  4.         //用StringBuffer，反转一下。
  5.         String text2=new StringBuffer(text1).reverse().toString();
  6.  
  7.          int[][] dp = new int[text1.length() + 1][text2.length() + 1]; // 先对dp数组做初始化操作
  8.         for (int i = 1 ; i <= text1.length() ; i++) {
  9.             char char1 = text1.charAt(i - 1);
  10.             for (int j = 1; j <= text2.length(); j++) {
  11.                 char char2 = text2.charAt(j - 1);
  12.                 if (char1 == char2) { // 开始列出状态转移方程
  13.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  14.                 } else {
  15.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  16.                 }
  17.             }
  18.         }
  19.         return dp[text1.length()][text2.length()];
  20.     }
  21. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/74369
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号