力扣动态规划入门21天刷题计划（共计46题）_力扣计划怎么提前做未解锁的天的题目

刷题地址：https://leetcode-cn.com/study-plan/dynamic-programming/?progress=8e97f6

动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。

使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

推荐阅读

一套框架解决「背包问题」

「代码随想录」带你学透完全背包！【139. 单词拆分】

知识点

子序列就是可以不连续，子串要连续
判断两个整数异号，用异或运算

动态规划填表格的在线网站：https://alchemist-al.com/algorithms/edit-distance

关于排列和组合的一些思考

类似下题，把1,3和和3,1看做是两种不同的组合，我们就可以吧这个题看做是青蛙跳台阶，先跳一步，再跳3步，先跳3步，再跳1步是两种不同的跳法。

但是实际上，组合是不可以重复的，1,3和3,1应该是相同的组合是两种不同的排列
那么我们求排列问题和组合问题的时候，就转化为背包问题的先遍历背包还是先遍历物品的问题了

参考：「代码随想录」带你搞定背包问题！518. 零钱兑换 II【附背包完整攻略】

2021.07.13(第1天)

1 509. 斐波那契数

class Solution {
    public int fib(int n) {
        int dp[]=new int[n+1];
        dp[0]=0;
        if(n<1)   return dp[0];
        dp[1]=1;    
        for(int i=2;i<n+1;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2 1137. 第 N 个泰波那契数

class Solution {
    public int tribonacci(int n) {
         int dp[]=new int[n+1];
         if(n==0) return 0;
         if(n==1) return 1;
         if(n==2) return 1;
         dp[0]=0; dp[1]=1; dp[2]=1;
         for(int i=3;i<n+1;i++)
         {
             dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
         }
          return dp[n];
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

空间优化

class Solution {
  public int tribonacci(int n) {
    if (n < 3) return n == 0 ? 0 : 1;

    int tmp, x = 0, y = 1, z = 1;
    for (int i = 3; i <= n; ++i) {
      tmp = x + y + z;
      x = y;
      y = z;
      z = tmp;
    }
    return z;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2021.07.14(第2天)

3 70. 爬楼梯

class Solution {
    public int climbStairs(int n) {
         int dp[]=new int [n];
         if(n==1) return 1;
         if(n==2) return 2;
         dp[0]=1;dp[1]=2;
         for(int i=2;i<n;i++)
         {
            dp[i]=dp[i-1]+dp[i-2];//先爬1级的方法数加上先爬2级的方法数
         }
         return dp[n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

递归解法，会超时

class Solution {
    public int climbStairs(int n) {
       if(n==1)  return 1;
       if(n==2)  return 2;    
       return climbStairs(n-1)+climbStairs(n-2);
    }
}
1
2
3
4
5
6
7

记忆化递归,还是超时

class Solution {
    public int climbStairs(int n) {
       if(n==1)  return 1;
       if(n==2)  return 2;    
       int dp[]=new int[n];
       dp[0]=1; dp[1]=2;
       if(dp[n-1]==0)
       {
          return climbStairs(n-1)+climbStairs(n-2);
       } 
       return  dp[n-1];      
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

记忆化递归2,还是超时

class Solution {
    public int climbStairs(int n) {
       if(n==1||n==0)  return 1;    
       int dp[]=new int[n+1];
       dp[0]=1; dp[1]=1;
       if(dp[n]==0)
       {
          return climbStairs(n-1)+climbStairs(n-2);
       } 
       return  dp[n];      
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

超时原因分析：dp数组是定义在递归里面的，发现了吗，，，，应该把递归数组定义在递归外面
下图这样？不行的,n都还没定义，不能给数组初始化大小

于是有聪明的小伙伴想到了重新构造一个函数，如下

class Solution {
  
    public int climbStairs(int n) {
        int dp[]=new int[n+1];
        dp[0]=1; dp[1]=1;
        helper(dp,n);
        return dp[n];
    }
    public int helper(int []dp,int n)
    {
      if(n==1||n==0)  return 1;               
       if(dp[n]==0)
       {
           dp[n]= helper(dp,n-1)+helper(dp,n-2);
       } 
       return  dp[n];        
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

用 Map做记忆化递归,可以的

class Solution {
   
     Map<Integer,Integer> cache = new HashMap();
    public int climbStairs(int n){
        if(n==0 || n==1){
            return 1;
        }
        if(cache.containsKey(n)){
            return cache.get(n);
        }
        int total = climbStairs(n-1)+climbStairs(n-2);
        cache.put(n,total);
        return total;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

节约空间的解法，用变量代替数组

class Solution {
    public int climbStairs(int n) {
       if(n==1)  return 1;
       if(n==2)  return 2;  
       int a=1,b=2,c=0;
       for(int i=2;i<n;i++)
       {
            c=a+b;
            a=b;
            b=c;
       }
       return c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4 746. 使用最小花费爬楼梯

这个题单是理解题就用了快半小时。。。就是注意cost[n]代表的是阶梯顶的前一个阶梯，也就是说你跳到cost[n]是需要支付cost[n]的体力值的，然后再一步登顶，你直接跳到cost[n-1]，再两步登顶，就不用支付cost[n]的体力值，但是要支付cost[n-1]

我们就求每一步的最小花费就好了。

思考过程
假设有2级台阶 [15,20] 那么对应的体力值就是最小的15了
假设有3级台阶 [15,20,10] 那么对应的体力值就是20了，因为15+10=25>20
假设有3级台阶 [15,20,3] 那么对应的体力值就是18了，因为15+3=18<20
那么就不能用每一级对应的最小花费来推出下一级的最小体力花费了

我想的是再用一个数组来存放到达每一级的最大花费，但是问题是不能对应跳的是一级还是2级

那我们就比较先跳一级的最小花费和先跳2级的最小花费？
比如有7级，我们可以比较6和5+cost[6]的大小
…
…
比如有3级 我们可以比较2和1+cost[2]的大小

dp[0]=cost[0]只有第0级台阶的时候，只有一种方法可以上楼
dp[1]=cost[1]有2级台阶的时候，最小花费是cost[1]有谁不服？一步登天的事没必要分两步走啊，这不是增加体力花费嘛。比如[1,100],要到达天花板，你直接从100上去就好了。。。先从1走，再走两步是到不了天花板的，只会被卡在天花板上，因为一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯 ，你从1开始走，只能先走100在上天花板。就要花费101了

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n ];
        dp[0] =cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i - 1] , dp[i - 2] )+ cost[i];           
        }
        return Math.min(dp[n - 1] , dp[n - 2] );
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

我又理解了一下题目，咱们可以构造一个dp数组存放到达每一级阶梯的最小花费，咱们先不管天花板，到达每一级的最小花费求出来了，则到达天花板的最小花费就是天花板前一级和天花板前两级的花费中最小的那个

dp[0]=cost[0];//到达第一级台阶的最小花费
dp[1]=cost[1];//到达第二级台阶的最小花费

第三级，可以从第一级跳上去，也可以从第二级跳上去，那么到达第三级的最小花费就是min(dp[0],dp[1])+cost[2],依次类推

参考「代码随想录」动态规划五步曲详细分析！746. 使用最小花费爬楼梯
一步一步推导动态规划的多种解法

2021.07.15（第3天）

5 198. 打家劫舍

个人分析：小偷每一次可以走多少步，可以走2，3,4，，，，n步，
可以从任意地方开始偷，
可以从第一家开始偷，也可以从第二家开始偷,但没必要从第三家开始偷吧，因为偷了第三家完全可以把第一家也偷了啊。。
现在分析[1,5,1,1,10]这种情况,小偷从第二家开始偷，直接走3步，偷第5家获得的利润将是最大
再分析[1,5,1,1,10,100]这种情况,小偷从第二家开始偷,先走2步，再走2步获得的利润将会最大

那么现在问题变成了每次走2步还是走3步的问题，没必要一次走4步，因为4可以拆分成先走2步再走2步，同理5=2+3，，，，，，，

理解拐了的嘛

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

空间优化

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

6 213. 打家劫舍 II

这个题跟上一题的区别就是打劫了第一家，就不能打劫最后一家，因为是环壮的嘛，所以可以分为打劫第一家和不打劫第一家两种情况进行讨论

class Solution {
    public int rob(int[] nums) {
        int N= nums.length;
        if(N==1) return nums[0];
        if(N==2) return Math.max(nums[0],nums[1]);
         int a=nums[0];
         int b=Math.max(nums[0],nums[1]);
         int sum1=0,sum2=0;
         sum1=b;
         for(int i=2;i<N-1;i++)//打劫第一家
         {
           sum1=Math.max(a+nums[i],b);
           a=b;
           b=sum1;
         }
       
         a=nums[1];b=Math.max(nums[1],nums[2]);
         sum2=b;
         for(int i=3;i<N;i++)//不打劫第一家
         {
           sum2=Math.max(a+nums[i],b);
           a=b;
           b=sum2; 
         }
         return Math.max(sum1,sum2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

把动态规划的代码合并到一个函数中

class Solution {
    public int rob(int[] nums) {
        int N= nums.length;
        if(N==1) return nums[0];
        if(N==2) return Math.max(nums[0],nums[1]);       
         return Math.max(robHelper(nums,0, N-1),robHelper(nums,1, N));
    }
    public int robHelper(int nums[],int begin,int end)
    {       
        int a=nums[begin];
        int b=Math.max(nums[begin],nums[begin+1]);
        int sum=b;
        for(int i=begin+2;i<end;i++)
        {
           sum=Math.max(a+nums[i],b); 
           a=b;
           b=sum;
        }     
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

7 740. 删除并获得点数

一开始思路出现问题，还以为是删掉所有这个等于nums[i]-1和nums[i]+1的数就行了，实际上不是，删掉这些数之后，剩下的数组里面也只能一个一个地取，还要接着删，题目给的例子太让人迷惑了，我的代码对于给的两个例子都能过，，，，，，，，，

class Solution {
    public int deleteAndEarn(int[] nums) {
        int N=nums.length;
        if(N==1) return nums[0];
        int dp[]=new int[N];
        int max=0;
        Map<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<N;i++){
         if(map.containsKey(nums[i]))//避免重复元素重复计算
         {
             dp[i]=map.get(nums[i]);
             continue;
         }
         for(int j=0;j<N;j++)
         {
             if((nums[j]!=nums[i]-1)&&(nums[j]!=nums[i]+1))
               dp[i]+=nums[j];
         }
          max=Math.max(dp[i],max);
          map.put(nums[i],dp[i]);
        }
      return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路：转换成打家劫舍问题

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    public int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

返回的sum数组就可以转成打家劫舍的数组了，即不能大打劫相邻的元素。

2021.07.16（第4天）

8 55. 跳跃游戏

如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。
可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。
如果可以一直跳到最后，就成功了。
作者：ikaruga
链接：https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这种方法所依据的核心特性：如果一个位置能够到达，那么这个位置左侧所有位置都能到达。 想到这一点，解法就呼之欲出了~

解释：i>k,即当前最大值k已经小于i了，说明不能到达第i个位置，也就不能到达后面的位置了

class Solution {
    public boolean canJump(int[] nums) {  
	     int N=nums.length;
         int k=0;//当前能达到的最大值
         for(int i=0;i<N;i++)
         {
            if(i>k)  return false;//不能到达i
            k=Math.max(k,i+nums[i]);          
         }
         return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

9 45. 跳跃游戏 II

移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int count=0;
        //当前的覆盖最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i==curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

7月17自己理解编写

class Solution {
    public int jump(int[] nums) {
        int maxCoverArea=0;
        int nextPos=0;
        int count=0;//跳跃次数
        if(nums.length==1) return 0;
        for(int i=0;i<nums.length;i++)
        {
            maxCoverArea=Math.max(i+nums[i], maxCoverArea);
           //当前能覆盖的最大区域等于或大于数组最后一个下标，再跳一步，然后就可以返回count了
            if(maxCoverArea>=nums.length-1) 
            {
                count++;
                break;
            }
          //当前能覆盖的最大区域小于数组最后一个下标，继续i遍历
           if(i==nextPos)
           {
               count++;
               nextPos=maxCoverArea;
           }

        }
       
       return count;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2021.07.17（第5天）

10 53. 最大子序和

贪心算法
当前指针所指元素之前的和小于0，则丢弃当前元素之前的序列

贪心算法

class Solution {
    public int maxSubArray(int[] nums) {
         //解题思路，当前指针之前的序列和小于0就丢弃，就是已经小于0的连续数列就不要参与后面的计算了
         int max=Integer.MIN_VALUE;//先让max取整数的最小值，避免数组中全是负数的情况
         if(nums.length==1) return nums[0];
         int curSum=nums[0];
         max=nums[0];//比如[-1,-2]这种
         for(int i=1;i<nums.length;i++)
         {
             if(curSum<0)//当前指针之前的序列和都小于0了，重置  curSum
             {
               curSum=nums[i];           
             } 
             else//当前指针之前的序列和大于等于0，直接加上 nums[i]
             {
               curSum=curSum+ nums[i]; 
             }
            max=Math.max(max,curSum);         
         }
         return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

简化一下，就是下面的代码

class Solution {
    public int maxSubArray(int[] nums) {
         //解题思路，当前指针之前的序列和小于0就丢弃，就是已经小于0的连续数列就不要参与后面的计算了
         int max=Integer.MIN_VALUE;//先让max取整数的最小值，避免数组中全是负数的情况
         if(nums.length==1) return nums[0];
         int curSum=nums[0];
         max=nums[0];//比如[-1,-2]这种
         for(int i=1;i<nums.length;i++)
         {                               
            curSum=Math.max(curSum+ nums[i],nums[i]); 
            max=Math.max(max,curSum);   
         }                   
         return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

动态规划

若前一个元素大于0，就将它加到当前元素上面

class Solution {
    public int maxSubArray(int[] nums) {
         //解题思路，当前指针之前的序列和小于0就丢弃，就是已经小于0的连续数列就不要参与后面的计算了，大于0就加到nums[i]上面
         
         int curSum=nums[0];
         int dp[]=new int[nums.length];
         dp[0]=nums[0];
         int max=nums[0];
         for(int i=1;i<nums.length;i++)
         {
            if(dp[i-1]>0)  dp[i]= dp[i-1]+nums[i];
            else dp[i]=nums[i];
            max=Math.max(dp[i],max);
         }        
     return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

其实想想，这个跟贪心算法的代码是一样的，不过可以省略dp数组，直接在原数组上面操作，节约空间，代码如下

class Solution {
    public int maxSubArray(int[] nums) {
         //解题思路，当前指针之前的序列和小于0就丢弃，就是已经小于0的连续数列就不要参与后面的计算了，大于0就加到nums[i]上面
        
         int curSum=nums[0];              
         int max=nums[0];
         for(int i=1;i<nums.length;i++)
         {
            if(nums[i-1]>0)  nums[i]=nums[i-1]+nums[i];          
            max=Math.max(nums[i],max);
         }        
     return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

11 918. 环形子数组的最大和

来不及了，直接抄的代码

class Solution {
   public int maxSubarraySumCircular(int[] A){
    // 情况一
    int maxSum = A[0];
    int sum = 0;
    for(int a : A){
        sum = a + Math.max(sum, 0);
        maxSum = Math.max(maxSum, sum);
    }
    // 情况二
    if(A.length > 2){
        int minSum = Integer.MAX_VALUE;
        sum = 0;
        for(int i = 1; i < A.length - 1; i++){
            sum = A[i] + Math.min(sum, 0);
            minSum = Math.min(minSum, sum);
        }
        int S = 0;
        for(int i = 0; i < A.length; i++){
            S += A[i];
        }
        maxSum = Math.max(maxSum, S - minSum);
    }

    return maxSum;
}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2021.07.18 （第6天）

12 152. 乘积最大子数组

定义一个最大值数组和最小值数组dp,分别表示数组中以当前元素结尾连续子数组乘积的最大值和最小值，因为负数遇到负数会反转，正数遇到负数也会反转，所以一旦遇到负数，maxSum和minSum中的值是需要相互用到的，maxSum[i]每次取乘积最大的， minSum[i]每次取乘积最小的。最后遍历maxSum数组就好了

class Solution {
    public int maxProduct(int[] nums) {
    //我的想法，遇到负数就先记着，累积2个就再乘起来
           //构造成绩最大和最小的数组
           int N=nums.length;
           if(N==1) return nums[0];
           int maxSum[]=new int[N];
           int minSum[]=new int[N];
           maxSum[0]=nums[0];
           minSum[0]=nums[0];
           for(int i=1;i<N;i++)
           {
               maxSum[i]=Math.max(maxSum[i-1]*nums[i],Math.max(nums[i],minSum[i-1]*nums[i]));
               minSum[i]=Math.min(minSum[i-1]*nums[i],Math.min(nums[i],maxSum[i-1]*nums[i]));
           }
           int max=Integer.MIN_VALUE;
           for(int i=0;i<N;i++)
           {
               max=Math.max(max, maxSum[i]);
           }
           return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

其实我有疑问就是遇到0应该怎么办

这是我以[2,3，-2,4，-5,0,2,200]测试出来的最后的结果

简化代码一直有错

经过Debug发现，是max取值有问题，以数组第一个元素结尾的子数组的最大乘积没有取到，应该 int max=nums[0];

class Solution {
    public int maxProduct(int[] nums) {
    //我的想法，遇到负数就先记着，累积2个就再乘起来
           //构造成绩最大和最小的数组
           int N=nums.length;
           if(N==1) return nums[0];
        //   int maxSum[]=new int[N];
        //   int minSum[]=new int[N];
           int a=nums[0];
           int b=nums[0];
           int max=nums[0];           
           int tmp=a;
           for(int i=1;i<N;i++)
           {
              a=Math.max(a*nums[i],Math.max(nums[i],b*nums[i]));
              max=Math.max(max, a); 
            
              b=Math.min(b*nums[i],Math.min(nums[i],tmp*nums[i]));
              tmp=a;//暂存a给b用
              
           }
         
           return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

13 1567. 乘积为正数的最长子数组长度

直接抄的代码提交的，看看思路，明早上去实验室复现

class Solution {
    public int getMaxLen(int[] nums) {
        int length = nums.length;
        int positive = nums[0] > 0 ? 1 : 0;
        int negative = nums[0] < 0 ? 1 : 0;
        int maxLength = positive;
        for (int i = 1; i < length; i++) {
            if (nums[i] > 0) {
                positive++;
                negative = negative > 0 ? negative + 1 : 0;
            } else if (nums[i] < 0) {
                int newPositive = negative > 0 ? negative + 1 : 0;
                int newNegative = positive + 1;
                positive = newPositive;
                negative = newNegative;
            } else {
                positive = 0;
                negative = 0;
            }
            maxLength = Math.max(maxLength, positive);
        }
        return maxLength;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

自己来悟的

class Solution {
    public int getMaxLen(int[] nums) {
     //我们用两个数组保存以当前数结尾乘积为正数的最长长度和乘积为负数的最长长度
     //以当前数结尾的乘积为正数的最长长度可以由positive[i-1]+1得到（nums[i]>0），
     //也可以由negative[i-1]+1得到（nums[i]<0）
     //同理以当前数结尾的乘积为负数的最长长度
      int length=nums.length;
      int positive[]=new int[length];
      int negative[]=new int[length];
        if (nums[0] > 0) {
            positive[0] = 1;
        } else if (nums[0] < 0) {
            negative[0] = 1;
        }
       int maxLength = positive[0];
      for(int i=1;i<length;i++)
      {
          if(nums[i]>0)
          {
             positive[i]=positive[i-1]+1; //正正得正 
             if( negative[i-1]!=0)//就是前一个negative[i-1]为0，那么 negative[i]也应该为0，不应该加1
             negative[i]=negative[i-1]+1;//负正得负 
          }
           else if(nums[i]<0)
          {
             if(negative[i-1]!=0)//就是前一个negative[i-1]为0，那么positive[i]也应该为0，不应该加1
             positive[i]=negative[i-1]+1; //负负得正 
             
            // if(positive[i-1]!=0)
             negative[i]=positive[i-1]+1;//负正得负 
          }
           else
          {
             positive[i]=0; //负负得正 
             negative[i]=0;//负正得负   
          }
      }
      for(int i=0;i<length;i++)
      {
        maxLength=Math.max(maxLength,positive[i]);
      }
      return maxLength;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2021.07.19 （第7天）

14 1014. 最佳观光组合

暴力解决

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

遍历优化

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
          int max=0; 
          int maxValues=values[0]+0;//最大的values[i]+i的值
          for(int i=1;i<values.length;i++)
          {
             maxValues=Math.max(maxValues,values[i-1]+i-1);//当前i之前的最大 maxValues
             max=Math.max(maxValues+values[i]-i,max);//当前i的maxValues+values[i]-i与max相比
          }
          return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0, mx = values[0] + 0;
        for (int j = 1; j < values.length; ++j) {
            ans = Math.max(ans, mx + values[j] - j);
            // 边遍历边维护
            mx = Math.max(mx, values[j] + j);
        }
        return ans;
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/best-sightseeing-pair/solution/zui-jia-guan-guang-zu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

15 121. 买卖股票的最佳时机

就是要考虑到利润为负数的时候不应该卖出股票，利润为0，
return maxprofit>0?maxprofit:0;

class Solution {
    public int maxProfit(int[] prices) {
        int min=prices[0];//最低价格
        int maxprofit=Integer.MIN_VALUE;//最大利润
        for(int i=1;i<prices.length;i++)
        {
            maxprofit=Math.max(maxprofit,prices[i]-min);
            min=Math.min(prices[i],min);
        }
        return maxprofit>0?maxprofit:0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

16 122. 买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
    //搜集所有的上坡
    int maxprofit=0;
    for(int i=1;i<prices.length;i++)
    {
        if(prices[i]-prices[i-1]>0)
        {
           maxprofit+=prices[i]-prices[i-1];
        }         
    }
     return maxprofit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

动态规划

就是分为当天结束手里有股票或者没有股票

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

贪心算法

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2021.07.20 (第8天)

17 309. 最佳买卖股票时机含冷冻期

class Solution {
    public int maxProfit(int[] prices) {
        //分为3种情况
        //1 当天结束手里有股票 2 当天结束手里没有股票，当天不是冷冻期 3 当天结束手里没有股票，当天为冷冻期
        int length=prices.length;
        int a[]=new int[length];//当天结束手里有股票
        int b[]=new int[length];//当天结束手里没有股票，当天结束不是冷冻期
        int c[]=new int[length];//当天结束后处于为冷冻期的最大收益
        a[0]=-prices[0]; b[0]=0; c[0]=0;
        //这里的「处于冷冻期」指的是在第 i 天结束之后的状态。也就是说：如果第 i 天结束之后处于冷冻期，那么第 i+1 天无法买入股票。
        for(int i=1;i<length;i++)
        {
           int  a1=Math.max(a[i-1],b[i-1]-prices[i]);//手里有一只股票可能情况为前一天手里就有一只股票，一直没卖，
            //也可能是前一天结束后不是冷冻期，今天买入
           int  b1=Math.max(b[i-1],c[i-1]);//手里没有股票且不是冷冻期，说明第i天没有任何操作，可能情况为前一天结束后为冷冻期，也可能是前一天结束后手里没有股票，当天结束不是冷冻期
           int  c1=a[i-1]+prices[i];//今天借宿后是冷冻期只可能是今天卖掉了一只股票，说明在第 i−1天时我们必须持有一支股票
            a[i]=a1;b[i]=b1;c[i]=c1;
        }
       return Math.max(b[length-1],c[length-1] );
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

18 714. 买卖股票的最佳时机含手续费

class Solution {
    public int maxProfit(int[] prices, int fee) {
        //分为当天结束手里有股票和手里没有股票的情况 如果有交易，就扣一次手续费
        int length=prices.length;
        int a[]=new int[length];//当天结束手里有股票
        int b[]=new int [length];//当天结束手里没有股票
        a[0]=-prices[0];
        b[0]=0;
        for(int i=1;i<length;i++)
        {
            int  a1=Math.max(a[i-1],b[i-1]-prices[i]);//当天结束手里有股票，可能是前一天手里有股票，也可能是今天买入了
            int b1=Math.max(b[i-1],a[i-1]+prices[i]-fee);//当天结束手里没有股票，可能是前一天有股票，今天卖出了，也可能是前一天手里就没有股票
            a[i]=a1;b[i]=b1;
        }
        return  b[length-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

空间优化

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int sell = 0, buy = -prices[0];
        for (int i = 1; i < n; ++i) {
            sell = Math.max(sell, buy + prices[i] - fee);
            buy = Math.max(buy, sell - prices[i]);
        }
        return sell;
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-han-sh-rzlz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

贪心算法
buy 表示在最大化收益的前提下，如果我们手上拥有一支股票，那么它的最低买入价格是多少。

即当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。在遍历完整个数组 prices 之后，我们就得到了最大的总收益。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < n; ++i) {
            if (prices[i] + fee < buy) {
                buy = prices[i] + fee;
            } else if (prices[i] > buy) {
                profit += prices[i] - buy;
                buy = prices[i];
            }
        }
        return profit;
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-han-sh-rzlz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2021.07.21（第9天）

19 139. 单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
       Set<String>set=new HashSet(wordDict);
       int n=s.length();
       int dp[]=new int[n+1];
       //用dp[i]表示以i结尾的s的子串能否由wordDict中的单词组成
       dp[0]=1;
       for(int i=1;i<=n;i++)
       {
           for(int j=0;j<i;j++)
           {
               if(dp[j]==1&&set.contains(s.substring(j,i)))
               {
                  dp[i]=1; 
                  break;
               }           
           }
       }
       return dp[n]==1?true:false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

优化
对于检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断，同时也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，如果分割点 j 到 i 的长度已经大于字典列表里最长的单词的长度，那么就结束枚举

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
参考
单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length(), maxw = 0;
        boolean[] dp = new boolean[len + 1]; 
        dp[0] = true;
        Set<String> set = new HashSet();
        for(String str : wordDict){
            set.add(str);
            maxw = Math.max(maxw, str.length());
        }
        for(int i = 1; i < len + 1; i++){
            for(int j = i; j >= 0 && j >= i - maxw; j--){
                if(dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

20 42. 接雨水

这个题是难题，有点来不及做了，也有点抗拒哈，先抄的答案过了，等会看一下视频，明天早上复现

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

2021.07.22(第10天)

21 413. 等差数列划分

暴力破解
枚举每一个i j 看是否满足，时间复杂度为o(n的3次方)

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
         int count=0;boolean flag=true;
          for(int i=0;i<nums.length-2;i++)//外层最多循环到倒数第二个元素，因为最少需要3个元素
          {            
              int temp=nums[i+1]-nums[i];
              for(int j=i+2;j<nums.length;j++)
              {   
                 flag=true;//尤其要注意这里，给每一个i对应的j都初始化一个 flag;             
                 for(int k=j-i;k>1;k--)
                 {
                     if((nums[i+k]-nums[i+k-1])!=temp)
                     {     
                         flag=false;  
                         break;                
                     }
                 }
                 if(flag) 
                 {
                   count++;                  
                 }          
              }
          }
          return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

暴力优化

加入i=3 j=5 如果满足条件 ，那么3到5是一个子序列，我们在判断6-5和5-4是否相等，如果相等，则3到6也是满足条件的一个子序列，这些序列都是以3开头的，不会和后面的重复

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
         int count=0;boolean flag=true;
          for(int i=0;i<nums.length-2;i++)//外层最多循环到倒数第二个元素，因为最少需要3个元素
          {            
              int temp=nums[i+1]-nums[i];
              for(int j=i+2;j<nums.length;j++)
              {                  
                if(nums[j]-nums[j-1]==temp) 
                {
                     count++;
                } 
                else  break;                                                      
              }
          }
          return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

动态规划
首先创建一个大小为 n 的一维数组 dp。dp[i] 用来存储在区间 (k,i) 而不在区间 (k,j) 中等差数列的个数，其中 j<i

比如 1 3 5 7 9 对于dp的下标2，他可以构成一个等差数列 ，对于下标3，新增的等差数列都是以下标3结尾的，有1 3 5 7 ， 3 5 7，即dp[i-1]+1,依次类推

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
         int count=0;        
         int dp[]=new int[nums.length];
         if(nums.length<3) return 0;
         dp[0]=0; dp[1]=0;
         for(int i=2;i<nums.length;i++)
         {
              if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2])
              {
                  dp[i]=dp[i-1]+1;
                  count=count+dp[i];
              }             
         }
         return count;         
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

动态规划空间优化

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
         int count=0;
         //用dp数组表示每一个下标能构成的等差出列的最大个数
         int dp=0;
         if(nums.length<3) return 0;
         
         for(int i=2;i<nums.length;i++)
         {
              if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2])
              {
                  dp=dp+1;
                  count=count+dp;
              }   
              else
              {
                  dp=0;
              }          
         }
         return count;
         
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

22 91. 解码方法

这个题也是抄的代码，明天复现

class Solution {
   public int numDecodings(String s) {

		if(s.charAt(0) == '0') {
			//说明无解
			return 0;
		}
		char[] charArray = s.toCharArray();
		int last_2 = 1, last_1 = 1;  //last_2 代表i-2  last_1 代表i-1 temp 代表当前
		for(int i=1; i<s.length(); i++) {
			int temp = last_1;
			
			if(charArray[i] == '0') {
				if(charArray[i-1] == '1' || charArray[i-1] == '2') {
					temp = last_2;
				}else {
					return 0;
				}
			}else if( charArray[i-1] == '1' || (charArray[i-1] == '2' && charArray[i] - '0'>0 && charArray[i] - '0'<7)) {
				temp += last_2;
			}
			last_2 = last_1;
			last_1 = temp;
		}
		return last_1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

参考：C++ 我认为很简单直观的解法

复现

class Solution {
    public int numDecodings(String s) {
        //这个题跟爬楼梯差不多，对于最后一个字符，它可以单独解码，也可以跟前一个字符混合解码
        //单独解码的时候，要求该字符不能为0，那么可解码总数就是前一个字符之前的可解码总数，即dp[n-1]
        //跟前一个字符混合解码的时候，要求前一个字符不能是0，不能超过2，当前一个字符为2的时候，最后一个字符不能超过6
        //跟前一个字符混合解码的时候,可解码的总数就是dp[n-2]
        //那么最后一个字符的可解码总数就是dp[n-2]+dp[n-1]
        //其他情况就不满足解码要求了，直接忽略
        if(s.length()==1&&s.charAt(0)=='0') return 0;
        if(s.length()==1&&s.charAt(0)!='0') return 1;
        int dp[]=new int[s.length()+1];
        dp[0]=1;
        for(int i=1;i<=s.length();i++)
        {
             if(s.charAt(i-1)!='0') dp[i]=dp[i-1];
             if (i >= 2 && (s.charAt(i - 2) == '1' || s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))
                dp[i] += dp[i - 2];

        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int numDecodings(string s) {
        if(s[0] == '0') return 0;
        int n = s.size();
        vector<int> dp(n+1,1);
        //dp[0]表示s[-1]的状态， dp[1] 表示 s[0]的状态
        //dp[i] 表示 s[i-1]的状态
        for(int i=2;i<=n;i++){
            if(s[i-1] == '0'){
                if(s[i-2] == '1' || s[i-2] == '2')//唯一译码，不增加情况
                    dp[i] = dp[i-2];
                else//这里要好好理解一下，比如给定340, 输出可行的编码数为0， 因为0和40都无法转换
                    return 0;
            }
            else if(s[i-2] == '1' || s[i-2] == '2' && s[i-1] >= '1' && s[i-1] <= '6')
                dp[i] = dp[i-1] + dp[i-2];
            else//当上述条件都不满足，维持上一个状态
                dp[i] = dp[i-1];
        }
        //for(auto c:dp) cout << c << ",";
        return dp[n];//返回dp[n] 即最后 s[n-1] 的状态
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2021.07.23（第11天）

23 264. 丑数 II

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) {
                p2++;
            }
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
        }
        return dp[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

24 96. 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
}
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2021.07.24（第12天）

25 118. 杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

26 119. 杨辉三角 II

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> C = new ArrayList<List<Integer>>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(C.get(i - 1).get(j - 1) + C.get(i - 1).get(j));
                }
            }
            C.add(row);
        }
        return C.get(rowIndex);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<Integer>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> cur = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
        }
        return pre;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2021.07.25 (第13天)

27 931. 下降路径最小和

这是我的第一版代码，还没有考虑边界以及剪枝，通不过

class Solution {
    public int minFallingPathSum(int[][] matrix) {
          int min=Integer.MIN_VALUE;
          for(int i=0;i<matrix[0].length;i++)
          {
              min=Math.min(dfs(matrix,0,i),min);
          }
         return min;
    }
    public int dfs(int [][]matrix,int i,int j)
    {
       if(i+1==matrix.length)
           return 0;
        return Math.min(dfs(matrix,i+1,j),Math.min(dfs(matrix,i+1,j+1),dfs(matrix,i+1,j-1)))+matrix[i][j];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这个能过

class Solution {
    public int minFallingPathSum(int[][] A) {
        int N = A.length;
        for (int r = N-2; r >= 0; --r) {
            for (int c = 0; c < N; ++c) {
                // best = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1])
                int best = A[r+1][c];
                if (c > 0)
                    best = Math.min(best, A[r+1][c-1]);
                if (c+1 < N)
                    best = Math.min(best, A[r+1][c+1]);
                A[r][c] += best;
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int x: A[0])
            ans = Math.min(ans, x);
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

28 120. 三角形最小路径和

暴力dfs 超时

顶点到底边的最小距离，可以转化为顶点的值加上与顶点相邻的两个节点中，到底边的距离最小的一个的距离值，
而与顶点相邻的两个节点中，到底边的距离最小的一个的距离值可以把这两个节点分别当作顶点，按同样的方式求解

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
          return dfs(triangle,0,0);
    }
    public  int dfs(List<List<Integer>> triangle,int i,int j)
    {
       if(i==triangle.size())
       {
           return 0;
       }
       return Math.min(dfs(triangle,i+1,j),dfs(triangle,i+1,j+1))+triangle.get(i).get(j);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

记忆化dfs

class Solution {
     Integer[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {        
          memo = new Integer[triangle.size()][triangle.size()];
          return dfs(triangle,0,0);
    }
    public  int dfs(List<List<Integer>> triangle,int i,int j)
    {
       if(i==triangle.size())
       {
           return 0;
       }      
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

参考

递归 + 记忆化 + DP， 本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】