力扣学习计划——动态规划入门 所有题目解法包含暴力递归以及dp的改造

股票、组合、背包、回文序列、公共序列、路径、打家劫舍、跳跃游戏、零钱

509斐波那契数

  1. // f(n) = f(n-1)+f(n-2)
  2.     // f(0) = 0
  3.     // f(1) = 1
  4.     public int fib(int n) {
  5.         if (n <= 1) return n;
  6.         int[] dp = new int[n+1];
  7.         dp[1] = 1;
  8.         for (int i = 2; i <= n; i++) {
  9.             dp[i] = dp[i-1]+dp[i-2];
  10.         }
  11.         return dp[n];
  12.     }
  14.     private int run(int n){
  15.         if (n <= 1){
  16.             return n;
  17.         }
  18.         return run(n-1)+run(n-2);
  19.     }

1137第N个泰波那契数

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

70爬楼梯

  1. public int climbStairs(int n) {
  2. //        return run(n,0);
  3.         if (n <= 2) return n;
  4.         int[] dp = new int[n+1];
  5.         dp[n-1] = 1;
  6.         dp[n-2] = 2;
  7.         for (int i = n-3; i >=0; i--) {
  8.             dp[i] = dp[i+1]+dp[i+2];
  9.         }
  10.         return dp[0];
  11.     }
  14.     // 从now到n有多少种方法
  15.     private int run(int n,int now){
  16.         if (now >= n){
  17.             return 0;
  18.         }
  19.         if (now == n-1){
  20.             return 1;
  21.         }
  22.         if (now == n-2){
  23.             return 2;
  24.         }
  25.         int v1 = run(n,now+1);
  26.         int v2 = run(n,now+2);
  27.         return v1+v2;
  28.     }

746使用最小花费爬楼梯

  1. public int minCostClimbingStairs(int[] cost) {
  2. //        return Math.min(run(cost,0),run(cost,1));
  3.         int n = cost.length;
  4.         int[] dp = new int[n+1];
  5.         dp[n-1] = cost[n-1];
  6.         dp[n-2] = cost[n-2];
  7.         for (int i = n-3; i >=0; i--) {
  8.             dp[i] = cost[i] + Math.min(dp[i+1],dp[i+2]);
  9.         }
  10.         return Math.min(dp[0],dp[1]);
  11.     }
  13.     //在index处爬到顶端的花费，target=cost.length
  14.     private int run(int[] cost,int index){
  15.         int n = cost.length;
  16.         // 到顶了
  17.         if (index == n){
  18.             return 0;
  19.         }
  20.         // 距离顶端不超过两格，一步跨过去
  21.         if (index >= n - 2){
  22.             return cost[index];
  23.         }
  25.         // 跨一步
  26.         int v1 = run(cost,index+1);
  27.         // 跨两步
  28.         int v2 = run(cost,index+2);
  29.         // 当前价值+最小价值
  30.         return cost[index] + Math.min(v1,v2);
  32.     }

198打家劫舍

  1. public int rob(int[] nums) {
  2. //        return run(nums,nums.length-1);
  3.         int n = nums.length;
  4.         if (n == 1) return nums[0];
  5.         int[] dp = new int[n];
  6.         dp[0] = nums[0];
  7.         dp[1] = Math.max(nums[0],nums[1]);
  8.         for (int i = 2; i < n; i++) {
  9.             // 偷index的,那么index-1不能偷，看到index-2的时候偷到了多少钱
  10.             int v1 = nums[i] + dp[i-2];
  11.             // 不偷index的，看index-1偷了多少钱就是当前偷了多少钱
  12.             int v2 = dp[i-1];
  13.             dp[i] = Math.max(v1,v2);
  14.         }
  15.         return dp[n-1];
  16.     }
  18.     // [0..index]时能偷到的最大金额
  19.     private int run(int[] nums,int index){
  20.         // 只有一个选择，肯定偷
  21.         if (index == 0){
  22.             return nums[0];
  23.         }
  24.         // 有两个，选最大的那个
  25.         if(index == 1){
  26.             return Math.max(nums[0],nums[1]);
  27.         }
  28.         // 偷index的,那么index-1不能偷，看到index-2的时候偷到了多少钱
  29.         int v1 = nums[index] + run(nums,index-2);
  30.         // 不偷index的，看index-1偷了多少钱就是当前偷了多少钱
  31.         int v2 = run(nums,index-1);
  33.         return Math.max(v1,v2);
  34.     }

213打家劫舍II

  1. public int rob(int[] nums) {
  2.         int n = nums.length;
  3.         if (n == 1) return nums[0];
  4.         if (n == 2) return Math.max(nums[0],nums[1]);
  5. //        return Math.max(run(nums,0,n-2),run(nums,1,n-1));
  6.         return Math.max(dp(nums,0)[n-2],dp(nums,1)[n-1]);
  7.     }
  9.     private int[] dp(int[] nums,int start){
  10.         int n = nums.length;
  11.         int[] dp = new int[n];
  12.         dp[start] = nums[start];
  13.         dp[start+1] = Math.max(nums[start],nums[start+1]);
  14.         for (int i = start+2; i <n; i++) {
  15.             // 偷index的,那么index-1不能偷，看到index-2的时候偷到了多少钱
  16.             int v1 = nums[i] + dp[i-2];
  17.             // 不偷index的，看index-1偷了多少钱就是当前偷了多少钱
  18.             int v2 = dp[i-1];
  19.             dp[i] = Math.max(v1,v2);
  20.         }
  21.         return dp;
  22.     }
  23.     // [0..index]时能偷到的最大金额
  24.     private int run(int[] nums,int start,int index){
  25.         // 只有一个选择，肯定偷
  26.         if (index == start){
  27.             return nums[start];
  28.         }
  29.         // 有两个，选最大的那个
  30.         if(index == start+1){
  31.             return Math.max(nums[start],nums[start+1]);
  32.         }
  33.         // 偷index的,那么index-1不能偷，看到index-2的时候偷到了多少钱
  34.         int v1 = nums[index] + run(nums,start,index-2);
  35.         // 不偷index的，看index-1偷了多少钱就是当前偷了多少钱
  36.         int v2 = run(nums,start,index-1);
  38.         return Math.max(v1,v2);
  39.     }

740删除并获得点数

  1. public int deleteAndEarn(int[] nums) {
  2.         if (nums.length == 1) return nums[0];
  3.         Arrays.sort(nums);
  4.         int[] array = new int[nums.length];
  5.         int pre = nums[0], sum = nums[0] , arrIndex = 0, arrStart = 0;
  6.         int ans = 0;
  7.         for (int i = 1; i < nums.length; i++) {
  8.             if (nums[i] == nums[i-1]){
  9.                 sum += nums[i];
  10.             }else if (nums[i] == nums[i-1] + 1){
  11.                 array[arrIndex++] = sum;
  12.                 pre = nums[i];
  13.                 sum = nums[i];
  14.             }else {
  15.                 array[arrIndex++] = sum;
  16.                 pre = nums[i];
  17.                 sum = nums[i];
  18.                 ans += dp(array,arrStart,arrIndex)[arrIndex-1];
  19.                 arrStart = arrIndex;
  20.             }
  21.         }
  22.         array[arrIndex++] = sum;
  23.         ans += dp(array,arrStart,arrIndex)[arrIndex-1];
  24.         return ans;
  25.     }
  27.     private int[] dp(int[] nums,int start,int end){
  28.         int n = nums.length;
  29.         int[] dp = new int[n];
  30.         dp[start] = nums[start];
  31.         if (start+1 < end){
  32.             dp[start+1] = Math.max(nums[start],nums[start+1]);
  33.             // 拿当前的
  34.             for (int i = start+2; i < end; i++) {
  35.                 int v1 = nums[i] + dp[i-2];
  36.                 int v2 = dp[i-1];
  37.                 dp[i] = Math.max(v1,v2);
  38.             }
  39.         }
  40.         return dp;
  41.     }
  43.     public int deleteAndEarn2(int[] nums) {
  44.         if (nums.length == 1) return nums[0];
  45.         Arrays.sort(nums);
  46.         int[] array = new int[nums.length];
  47.         int pre = nums[0], sum = nums[0] , arrIndex = 0, arrStart = 0;
  48.         int ans = 0;
  49.         for (int i = 1; i < nums.length; i++) {
  50.             if (nums[i] == nums[i-1]){
  51.                 sum += nums[i];
  52.             }else if (nums[i] == nums[i-1] + 1){
  53.                 array[arrIndex++] = sum;
  54.                 pre = nums[i];
  55.                 sum = nums[i];
  56.             }else {
  57.                 array[arrIndex++] = sum;
  58.                 pre = nums[i];
  59.                 sum = nums[i];
  60.                 ans += run(array,arrStart,arrIndex-1);
  61.                 arrStart = arrIndex;
  62.             }
  63.         }
  64.         array[arrIndex++] = sum;
  65.         ans += run(array,arrStart,arrIndex-1);
  66.         return ans;
  67.     }
  69.     // nums: 值连续的数组，合并之后得到的新数组
  70.     // index: 当前的nums的位置
  71.     // [0..index]能拿到的最大值
  72.     private int run(int[] nums,int start,int index){
  73.         if (index < start){
  74.             return 0;
  75.         }
  76.         if (index == start){
  77.             return nums[start];
  78.         }
  79.         if(index == start+1){
  80.             return Math.max(nums[start],nums[start+1]);
  81.         }
  82.         // 拿当前的
  83.         int v1 = nums[index] + run(nums,start,index-2);
  84.         int v2 = run(nums,start,index-1);
  85.         return Math.max(v1,v2);
  86.     }

55跳跃游戏

  1. public boolean canJump(int[] nums) {
  2. //        return run(nums,0);
  3.         boolean[] dp = new boolean[nums.length];
  4.         dp[nums.length-1] = true;
  5.         for (int i = nums.length-2; i >= 0; i--) {
  6.             int step = nums[i];
  7.             if (nums[i] == 0) continue;
  8.             boolean can = false;
  9.             for (int j = 1; j <= step; j++) {
  10.                 can = can | (i+j >= nums.length-1 ? true : dp[i+j]);
  11.                 dp[i] = can;
  12.             }
  13.         }
  14.         return dp[0];
  15.     }
  17.     // 从cur开始跳能不能跳上去
  18.     private boolean run(int[] nums,int cur){
  19.         // 当前位置大于等于最后位置的，都算能跳上来
  20.         if (cur >= nums.length-1){
  21.             return true;
  22.         }
  23.         int step = nums[cur];
  24.         // 如果当前位置能跳0，肯定不行
  25.         if (step == 0) return false;
  26.         boolean can = false;
  27.         for (int i = 1; i <= step; i++) {
  28.             can |= run(nums,cur+i);
  29.             if (can) return true;
  30.         }
  31.         return false;
  32.     }

45跳跃游戏II

  1. public int jump(int[] nums) {
  2. //        return run(nums,0);
  3.         int[] dp = new int[nums.length];
  4.         int n = nums.length;
  5.         // 显式设置一下base case，下面循环可以从n-2开始
  6.         dp[n-1] = 0;
  7.         for (int i = n-2; i >= 0; i--) {
  8.             int step = nums[i];
  9.             // 这里跳不上去了，返回个-1代表此路不通
  10.             if (step == 0){
  11.                 dp[i] = -1;
  12.                 continue;
  13.             }
  14.             int min = Integer.MAX_VALUE;
  15.             // 算下后面的最少需要多少次
  16.             for (int j = 1; j <= step; j++) {
  17.                 int next = (i + j) >= n-1 ? 0 : dp[i+j];
  18.                 // -1的结果舍弃掉
  19.                 if (next >= 0){
  20.                     min = Math.min(next,min);
  21.                 }
  22.             }
  23.             dp[i] = min+1;
  24.         }
  25.         return dp[0];
  26.     }
  29.     // 从cur跳到顶部需要的最少步数
  30.     private int run(int[] nums,int cur){
  31.         int n = nums.length;
  32.         // 已经到了顶端，还需要0次
  33.         if (cur >= n-1){
  34.             return 0;
  35.         }
  36.         int step = nums[cur];
  37.         // 这里跳不上去了，返回个-1代表此路不通
  38.         if (step == 0){
  39.             return -1;
  40.         }
  41.         int min = Integer.MAX_VALUE;
  42.         // 算下后面的最少需要多少次
  43.         for (int i = 1; i <= step; i++) {
  44.             int next = run(nums,cur+i);
  45.             // -1的结果舍弃掉
  46.             if (next >= 0){
  47.                 min = Math.min(next,min);
  48.             }
  49.         }
  50.         return 1+min;
  51.     }

53最大子数组和

  1. public int maxSubArray(int[] nums) {
  2.         int n = nums.length;
  3.         if (n == 1) return nums[0];
  4.         int[] dp = new int[n];
  5.         dp[0] = nums[0];
  6.         for (int i = 1; i < n; i++) {
  7.             dp[i]= Math.max(nums[i],nums[i]+dp[i-1]);
  8.         }
  9.         return Arrays.stream(dp).max().getAsInt();
  10.     }
  12.     public int maxSubArray2(int[] nums) {
  13.         if (nums.length == 1) return nums[0];
  14.         max = nums[0];
  15.         run(nums,nums.length-1);
  16.         return max;
  17.     }
  19.     private int max = Integer.MIN_VALUE;
  21.     // 截止到cur的最大连续子数组和
  22.     // 注意拥有最大连续和的子数组并不一定是以nums[n-1]结尾的
  23.     // curMax代表一定以cur为结尾的最大连续子数组和
  24.     // max代表在cur之前但不一定以cur结尾的最大连续子数组和
  25.     private int run(int[] nums,int cur){
  26.         int curMax = 0;
  27.         if (cur == 0){
  28.             curMax = nums[0];
  29.         }else {
  30.             curMax= Math.max(nums[cur],nums[cur]+run(nums,cur-1));
  31.         }
  32.         max = Math.max(curMax,max);
  33.         return curMax;
  34.     }

918环形子数组的最大和

  1. public int maxSubarraySumCircular(int[] nums) {
  2.         if (nums.length == 1) return nums[0];
  3.         int[] dp1 = new int[nums.length];
  4.         int[] dp2 = new int[nums.length];
  6.         dp1[0] = dp2[0] = nums[0];
  7.         int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
  8.         for (int i = 1; i < nums.length; i++) {
  9.             dp1[i] = Math.min(nums[i],dp1[i-1]+nums[i]);
  10.             dp2[i] = Math.max(nums[i],dp2[i-1]+nums[i]);
  11.             min = Math.min(dp1[i],min);
  12.             max = Math.max(dp2[i],max);
  13.         }
  14.         int sum = Arrays.stream(nums).sum();
  15.         // 防止全部都是负数的情况
  16.         return sum == min ? max : Math.max(max, sum - min);
  17.     }
  19.     private int min = Integer.MAX_VALUE;
  20.     private int max = Integer.MIN_VALUE;
  22.     // 如果最大连续子数组位于数组中间，则正常求最大连续子数组和即可
  23.     // 如果最大的分布在两端，则正常求最小连续子数组和，用总和减去最小和即可
  24.     public int maxSubarraySumCircular2(int[] nums) {
  25.         if (nums.length == 1) return nums[0];
  26.         run1(nums,nums.length-1);
  27.         run2(nums,nums.length-1);
  28.         int sum = Arrays.stream(nums).sum();
  29.         return sum == min ? max : Math.max(max, sum - min);
  30.     }
  32.     // 以cur结尾的连续数组最小和
  33.     private int run1(int[] nums,int cur){
  34.         int curMin = Integer.MAX_VALUE;
  35.         if (cur == 0){
  36.             curMin = nums[0];
  37.         }else {
  38.             curMin = Math.min(nums[cur],run1(nums,cur-1)+nums[cur]);
  39.         }
  40.         min = Math.min(min,curMin);
  41.         return curMin;
  42.     }
  43.     // 以cur结尾的连续数组最大和
  44.     private int run2(int[] nums,int cur){
  45.         int curMax = Integer.MIN_VALUE;
  46.         if (cur == 0){
  47.             curMax = nums[0];
  48.         }else if (cur == 1){
  49.             curMax = Math.max(Math.max(nums[0],nums[1]),nums[0]+nums[1]);
  50.         }else {
  51.             curMax = Math.max(nums[cur],run2(nums,cur-1)+nums[cur]);
  52.         }
  53.         max = Math.max(max,curMax);
  54.         return curMax;
  55.     }

152乘积最大子数组

  1. public int maxProduct(int[] nums) {
  2.         if (nums.length == 1) return nums[0];
  3.         int ans = nums[0];
  4.         int[] max = new int[nums.length];
  5.         int[] min = new int[nums.length];
  6.         max[0] = min[0] = nums[0];
  7.         for (int i = 1; i < nums.length; i++) {
  8.             max[i] = Math.max(nums[i],Math.max(max[i-1]*nums[i],min[i-1]*nums[i]));
  9.             min[i] = Math.min(nums[i],Math.min(max[i-1]*nums[i],min[i-1]*nums[i]));
  10.             ans = Math.max(max[i],ans);
  11.         }
  12.         return ans;
  13.     }
  15.     public int maxProduct2(int[] nums) {
  16.         run(nums,nums.length-1);
  17.         min = max = nums[0];
  18.         return max;
  19.     }
  21.     private Integer min;
  22.     private Integer max;
  24.     // 以index为结尾的连续数组的最大值和最小值
  25.     private int[] run(int[] nums,int index){
  26.         if (index == 0){
  27.             return new int[]{nums[0],nums[0]};
  28.         }
  29.         int[] next = run(nums,index-1);
  30.         // 当前index结尾的最大值要么是自身，要么是自身和index-1处的最大值的乘积，或者当前值是负的，最大值为当前值和index-1最小值乘积
  31.         // 注意由于有负负得正的情况，next[0] > next[1] 不一定代表next[0]*nums[index]>next[1]*nums[index]
  32.         int mx = Math.max(nums[index],Math.max(next[0]*nums[index],next[1]*nums[index]));
  33.         int mn = Math.min(nums[index],Math.min(next[0] * nums[index],next[1] * nums[index]));
  34.         max = Math.max(mx,max);
  35.         min = Math.min(mn,min);
  36.         return new int[]{mx,mn};
  37.     }

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

  1. public int getMaxLen(int[] nums) {
  2.         if (nums.length == 1) return nums[0] > 0 ? 1 : 0;
  3.         int[][] dp = new int[nums.length][2];
  4.         int[] start = nums[0] > 0 ? new int[]{1,0} : nums[0] == 0 ? new int[]{0,0} : new int[]{0,1};
  5.         dp[0] = start;
  6.         int ans = Integer.MIN_VALUE;
  7.         for (int i = 1; i < nums.length; i++) {
  8.             int[] next = dp[i-1];
  9.             int[] cur = new int[2];
  10.             if (nums[i] > 0){
  11.                 // 当前是正数，正数长度 = 原来正数长度直接+1，即使没有正数，自身也能构成长度为1的正数
  12.                 // 负数长度 = 如果原来有负数，该正数添上能让负数长度+1。但如果原来没用负数，该正数无法增加负数长度
  13.                 cur[0] = next[0] + 1;
  14.                 cur[1] = next[1] == 0 ? 0 : next[1]+1;
  15.             }else if (nums[i] < 0){
  16.                 // 当前是负数，负数长度是原来正数长度+1，即使没有正数，自身也能构成长度为1的负数
  17.                 // 正数长度 = 如果原来有负数，长度+1。但如果原来没用负数，该负数无法增加正数长度
  18.                 cur[1] = next[0] + 1;
  19.                 cur[0] = next[1] == 0 ? 0 : next[1] + 1;
  20.             }
  21.             ans = Math.max(cur[0],ans);
  22.             dp[i] = cur;
  23.         }
  24.         return ans;
  25.     }
  27.     public int getMaxLen2(int[] nums) {
  28.         if (nums.length == 1) return nums[0] > 0 ? 1 : 0;
  29.         int[] ans = run(nums,nums.length-1);
  30.         return max;
  31.     }
  33.     // 以index为结尾的连续子数组
  34.     // [0] index结尾乘积为正数的长度
  35.     // [1] index结尾乘积为负数的长度
  36.     private int max = 0;
  37.     private int[] run(int[] nums,int index){
  38.         if (index == 0){
  39.             return nums[0] > 0 ? new int[]{1,0} : nums[0] == 0 ? new int[]{0,0} : new int[]{0,1};
  40.         }
  41.         int[] next = run(nums,index-1);
  42.         int[] cur = new int[2];
  43.         if (nums[index] > 0){
  44.             // 当前是正数，正数长度 = 原来正数长度直接+1，即使没有正数，自身也能构成长度为1的正数
  45.             // 负数长度 = 如果原来有负数，该正数添上能让负数长度+1。但如果原来没用负数，该正数无法增加负数长度
  46.             cur[0] = next[0] + 1;
  47.             cur[1] = next[1] == 0 ? 0 : next[1]+1;
  48.         }else if (nums[index] < 0){
  49.             // 当前是负数，负数长度是原来正数长度+1，即使没有正数，自身也能构成长度为1的负数
  50.             // 正数长度 = 如果原来有负数，长度+1。但如果原来没用负数，该负数无法增加正数长度
  51.             cur[1] = next[0] + 1;
  52.             cur[0] = next[1] == 0 ? 0 : next[1] + 1;
  53.         }
  54.         max = Math.max(cur[0],max);
  55.         return cur;
  56.     }

1014最佳观光组合

  1. public int maxScoreSightseeingPair2(int[] values) {
  2.         int n = values.length;
  3.         int[][] dp = new int[n][n];
  4.         dp[0][1] = dp[1][0] = values[0] + values[1] -1;
  5.         for (int i = 1; i < n -1; i++) {
  6.             dp[i][i+1] = values[i] + values[i+1]-1;
  7.             dp[i][i-1] = values[i] + values[i-1]-1;
  8.         }
  9.         dp[n -1][n -2] = values[n-1] + values[n-2] -1;
  11. //        for (int i = 0; i < values.length; i++) {
  12. //            for (int j = 0; j < values.length; j++) {
  13. //                if (Math.abs(i - j) == 1){
  14. //                    dp[i][j] = values[i] + values[j] - 1;
  15. //                }
  16. //            }
  17. //        }
  19.         // dp[i][j] 与 左、下、左下和自身对比，因此画图可以看出遍历顺序
  20.         // 优化下可以不用对比左下，因为左比左下大，下也比左下大
  21.         for (int i = values.length-3; i >=0 ; i--) {
  22.             for (int j = i+2; j < values.length; j++) {
  23.                 // v1 可以省略
  24.                 int v1 = dp[i+1][j-1];
  25.                 int v2 = dp[i][j-1];
  26.                 int v3 = dp[i+1][j];
  27.                 int v4 = values[i] + values[j] + i - j;
  28.                 dp[i][j] = Math.max(Math.max(v1,v2),Math.max(v3,v4));
  29.             }
  30.         }
  31.         return dp[0][n -1];
  32.     }
  34.     public int maxScoreSightseeingPair2(int[] values) {
  35.         return run(values,0,values.length-1);
  36.     }
  39.     // [start...end] 之间的最佳组合分数
  40.     private int run(int[] values,int start,int end){
  41.         if (start < 0 || end == values.length || start >= end){
  42.             return 0;
  43.         }
  44.         if (Math.abs(start - end) == 1){
  45.             return values[start]+values[end]-1;
  46.         }
  47.         // 一定不以start和end为两端
  48.         // 可能以start为左端，一定不以end为右端
  49.         // 可能以end为右端，一定不以start为左端
  50.         // 一定以start和end为两端
  51.         int v1 = run(values,start+1,end-1);
  52.         int v2 = run(values,start,end-1);
  53.         int v3 = run(values,start+1,end);
  54.         int v4 = values[start] + values[end] + start - end;
  55.         return Math.max(Math.max(v1,v2),Math.max(v3,v4));
  56.     }
  1. // 上面时间复杂度是O(n2)，可以进一步优化
  2. // 对于公式value[i]+value[j]+i-j
  3. // 对于j的答案，即[0...j-1]与j组成的最大值即value[i]+i的最大值
  4. // j与后面组成的组合会包含在j取后面的值的情况中
  5. class Solution {
  6.     public int maxScoreSightseeingPair(int[] values) {
  7.         int ans = 0, mx = values[0] + 0;
  8.         for (int j = 1; j < values.length; ++j) {
  9.             ans = Math.max(ans, mx + values[j] - j);
  10.             // 边遍历边维护
  11.             mx = Math.max(mx, values[j] + j);
  12.         }
  13.         return ans;
  14.     }
  15. }

121股票买卖最佳时机

  1. public int maxProfit(int[] prices) {
  2.         if (prices.length <= 1) return 0;
  3.         int[][] dp = new int[prices.length][2];
  4.         dp[0][0] = prices[0];
  5.         for (int i = 1; i < prices.length; i++) {
  6.             dp[i][1] = Math.max(dp[i-1][1],prices[i] - dp[i-1][0]);
  7.             dp[i][0] = Math.min(dp[i-1][0],prices[i]);
  8.         }
  9.         return dp[prices.length-1][1];
  11.     }
  14.     public int maxProfit2(int[] prices) {
  15.         if (prices.length <= 1) return 0;
  16.         return run(prices,prices.length-1)[1];
  17.     }
  19.     // [0] 截止到index最低的买入价格
  20.     // [1] index及之前能卖出的最大价格
  21.     private int[] run(int[] prices,int index){
  22.         if (index == 0){
  23.             return new int[]{prices[0],0};
  24.         }
  25.         int[] next = run(prices,index-1);
  26.         next[1] = Math.max(next[1],prices[index] - next[0]);
  27.         next[0] = Math.min(next[0],prices[index]);
  28.         return next;
  29.     }

122买卖股票的最佳时机II

  1. public int maxProfit(int[] prices) {
  2.         if (prices.length <= 1) return 0;
  3.         int[][]dp = new int[prices.length][2];
  4.         dp[0][1] = -prices[0];
  5.         for (int i = 1; i < prices.length; i++) {
  6.             dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
  7.             dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
  8.         }
  9.         return dp[prices.length-1][0];
  10.     }
  12.     public int maxProfit2(int[] prices) {
  13.         if (prices.length <= 1) return 0;
  14.         return run(prices,prices.length-1)[0];
  15.     }
  17.     // 到index天
  18.     // [0] 手里没股票的最大利润
  19.     // [1] 手里有股票的最大利润
  20.     private int[] run(int[] prices,int index){
  21.         if (index == 0){
  22.             return new int[]{0,-prices[0]};
  23.         }
  24.         int[] next = run(prices,index-1);
  25.         // 没股票 = 之前就没股票或者之前有股票现在卖掉
  26.         int v1 = Math.max(next[0],prices[index]+next[1]);
  27.         // 有股票 = 之前有股票或者之前没股票现在买一只
  28.         int v2 = Math.max(next[1],next[0]-prices[index]);
  30.         return new int[]{v1,v2};
  31.     }

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

  1. public int maxProfit(int[] prices) {
  2.         int[][] dp = new int[prices.length][3];
  3.         dp[0][0] = -prices[0];
  4.         for (int i = 1; i < prices.length; i++) {
  5.             int[] next = dp[i-1];
  6.             int v1 = Math.max(next[0],next[1]-prices[i]);
  7.             // 不持有股票且不在冷冻期 = 前面 没有且不在冷冻期/不持有股票处于冷冻期利润
  8.             int v2 = Math.max(next[1],next[2]);
  9.             // 不持有股票处于冷冻期利润 = 前面有股票当前卖出
  10.             int v3 = next[0] + prices[i];
  11.             dp[i] = new int[]{v1,v2,v3};
  12.         }
  13.         return Math.max(dp[prices.length-1][1],dp[prices.length-1][2]);
  15.     }
  17.     public int maxProfit2(int[] prices) {
  18.         int[] ans = run(prices,prices.length-1);
  19.         return Math.max(ans[1],ans[2]);
  20.     }
  23.     // [0] 持有股票最大利润
  24.     // [1] 不持有股票且不在冷冻期利润
  25.     // [2] 当前不持有股票处于冷冻期利润
  26.     private int[] run(int[] prices,int index){
  27.         if (index == 0){
  28.             return new int[]{-prices[0],0,0};
  29.         }
  30.         int[] next = run(prices,index-1);
  31.         // 持有股票 = 之前没有当前买入/之前有
  32.         int v1 = Math.max(next[0],next[1]-prices[index]);
  33.         // 不持有股票且不在冷冻期 = 前面 没有且不在冷冻期/不持有股票处于冷冻期利润
  34.         int v2 = Math.max(next[1],next[2]);
  35.         // 不持有股票处于冷冻期利润 = 前面有股票当前卖出,这里状态是当index天结束时处于冷冻期，后面index+1不能买入
  36.         int v3 = next[0] + prices[index];
  38.         return new int[]{v1,v2,v3};
  39.     }

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

  1. public int maxProfit(int[] prices, int fee) {
  2.         if (prices.length <= 1) return 0;
  3.         int[][] dp = new int[prices.length][2];
  4.         dp[0][0] = -prices[0];
  5.         for (int i = 1; i < prices.length; i++) {
  6.             int[] next = dp[i-1];
  7.             // 持有 = 前面持有无操作 | 前面不持有当前买入
  8.             int v1 = Math.max(next[0],next[1] - prices[i]);
  9.             // 不持有 = 前面不持有 | 前面持有卖出减去手续费
  10.             int v2 = Math.max(next[1],next[0] + prices[i] - fee);
  11.             dp[i] = new int[]{v1,v2};
  12.         }
  13.         return dp[prices.length-1][1];
  14.     }
  17.     public int maxProfit2(int[] prices, int fee) {
  18.         if (prices.length <= 1) return 0;
  19.         return run(prices,fee,prices.length-1)[1];
  20.     }
  22.     // [0] 持有
  23.     // [1] 不持有
  24.     private int[] run(int[] prices, int fee,int index){
  25.         if (index == 0){
  26.             return new int[]{-prices[0],0};
  27.         }
  28.         int[] next = run(prices,fee,index-1);
  29.         // 持有 = 前面持有无操作 | 前面不持有当前买入
  30.         int v1 = Math.max(next[0],next[1] - prices[index]);
  31.         // 不持有 = 前面不持有 | 前面持有卖出减去手续费
  32.         int v2 = Math.max(next[1],next[0] + prices[index] - fee);
  34.         return new int[]{v1,v2};
  35.     }

139单词拆分

  1. public boolean wordBreak(String s, List<String> wordDict) {
  2.         int n = s.length();
  3.         Set<String> wd = new HashSet<>(wordDict.size());
  4.         int max = Integer.MIN_VALUE;
  5.         // 记录下字典里的最长长度
  6.         for (String st : wordDict) {
  7.             wd.add(st);
  8.             max = Math.max(st.length(),max);
  9.         }
  10.         boolean[] dp = new boolean[n+1];
  11.         char[] str = s.toCharArray();
  12.         dp[n] = true;
  13.         dp[n-1] = wd.contains(str[n-1]+"");
  14.         for (int i = n-2; i >= 0; i--) {
  15.             StringBuilder builder = new StringBuilder();
  16.             for (int j = i; j < n; j++) {
  17.                 //长度比字典最长的词还长直接截断
  18.                 if (builder.length() > max){
  19.                     break;
  20.                 }
  21.                 builder.append(str[j]);
  22.                 if (wd.contains(builder.toString())){
  23.                     boolean ok = dp[j+1];
  24.                     if (ok){
  25.                         dp[i] = true;
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.         return dp[0];
  31.     }
  33.     public boolean wordBreak2(String s, List<String> wordDict) {
  34.         Set<String> wd = new HashSet<>(wordDict);
  35.         return run(s.toCharArray(),wd,0);
  36.     }
  38.     // str从start到结尾能否构成
  39.     private boolean run(char[] str,Set<String> wd,int start){
  40.         int n = str.length;
  41.         // 能到达这里说明前面的都是符合条件递归进来的，所以直接返回true
  42.         if (start == n) return true;
  43.         StringBuilder builder = new StringBuilder();
  44.         for (int i = start; i < n; i++) {
  45.             builder.append(str[i]);
  46.             if (wd.contains(builder.toString())){
  47.                 boolean ok = run(str,wd,i+1);
  48.                 if (ok){
  49.                     return true;
  50.                 }
  51.             }
  52.         }
  53.         return false;
  54.     }

42接雨水

  1. public int trap(int[] height) {
  2.         int n = height.length;
  3.         int[] leftMax = new int[n];
  4.         int[] rightMax = new int[n];
  5.         leftMax[0] = height[0];
  6.         rightMax[n-1] = height[n-1];
  7.         for (int i = 1; i < n; i++) {
  8.             leftMax[i] = Math.max(leftMax[i-1],height[i]);
  9.         }
  10.         for (int i = n-2; i >=0; i--) {
  11.             rightMax[i] = Math.max(rightMax[i+1],height[i]);
  12.         }
  13.         int ans = 0;
  14.         for (int i = 0; i < n; i++) {
  15.             ans += (Math.min(leftMax[i],rightMax[i]) - height[i]);
  16.         }
  17.         return ans;
  18.     }

413等差数列划分

  1. public int numberOfArithmeticSlices(int[] nums) {
  2.         if (nums.length < 3) return 0;
  3.         int ans = 0 , c = 0;
  4.         int[] dp = new int[nums.length];
  5.         for (int i = 2; i < nums.length; i++) {
  6.             int next = dp[i-1];
  7.             if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){
  8.                 c = 1 + next;
  9.                 ans += c;
  10.                 dp[i] = c;
  11.             }
  12.         }
  13.         return ans;
  14.     }
  17.     public int numberOfArithmeticSlices2(int[] nums) {
  18.         if (nums.length < 3) return 0;
  19.         run(nums,nums.length-1);
  20.         return count;
  21.     }
  23.     private int count = 0;
  25.     // 以end为结尾的等差数列的数量。
  26.     private int run(int[] nums,int end){
  27.         if (end < 2){
  28.             return 0;
  29.         }
  30.         int c = 0;
  31.         // 先判断前面的有几个
  32.         int next = run(nums,end-1);
  33.         // 如果end和前面的构成等差数列，除了新增一个end-2,end-1,end这个新等差数列
  34.         // 前面end-1处的所有等差数列后面都加一个end，构成长度最小为4的新的等差数列
  35.         if (nums[end] - nums[end-1] == nums[end-1] - nums[end-2]){
  36.             c = 1 + next;
  37.             count += c;
  38.         }
  39.         return c;
  40.     }

91解码方法

  1. public int numDecodings(String s) {
  2.         int n = s.length();
  3.         int[] dp = new int[n+1];
  4.         char[] str = s.toCharArray();
  5.         dp[n] = 1;
  6.         for (int i = n-1; i >=0; i--) {
  7.             if (str[i] == '0'){
  8.                 dp[i] = 0;
  9.                 continue;
  10.             }
  11.             //解码index,下一个就是index+1
  12.             int v1 = dp[i+1];
  13.             //解码index和index+1,但这个两位数不能超过26
  14.             int v2 = 0;
  15.             if (i+1 < str.length && ((str[i] - '0') * 10 + (str[i+1] - '0')) < 27){
  16.                 v2 = dp[i+2];
  17.             }
  18.             dp[i] = v1 + v2;
  19.         }
  20.         return dp[0];
  21.     }
  23.     public int numDecodings2(String s) {
  24.         return run(s.toCharArray(),0);
  25.     }
  27.     //[index...n]有几种方式
  28.     private int run(char[] str,int index){
  29.         //到头了，当前路径有效，返回有效方式1
  30.         if (index == str.length){
  31.             return 1;
  32.         }
  33.         //如果当前位置数字是0，则肯定无效，直接返回0
  34.         if (str[index] == '0'){
  35.             return 0;
  36.         }
  37.         //解码index,下一个就是index+1
  38.         int v1 = run(str,index+1);
  39.         //解码index和index+1,但这个两位数不能超过26
  40.         int v2 = 0;
  42.         if (index+1 < str.length && ((str[index] - '0') * 10 + (str[index+1] - '0')) < 27){
  43.             v2 = run(str,index+2);
  44.         }
  45.         return v1 + v2;
  46.     }

264丑数II

  1. class Solution {
  2.     public int nthUglyNumber(int n) {
  3.         int[] factors = {2, 3, 5};
  4.         Set<Long> seen = new HashSet<Long>();
  5.         PriorityQueue<Long> heap = new PriorityQueue<Long>();
  6.         seen.add(1L);
  7.         heap.offer(1L);
  8.         int ugly = 0;
  9.         for (int i = 0; i < n; i++) {
  10.             long curr = heap.poll();
  11.             ugly = (int) curr;
  12.             for (int factor : factors) {
  13.                 long next = curr * factor;
  14.                 if (seen.add(next)) {
  15.                     heap.offer(next);
  16.                 }
  17.             }
  18.         }
  19.         return ugly;
  20.     }
  21. }
  23. public int nthUglyNumber(int n) {
  24.         int[] dp = new int[n + 1];
  25.         dp[1] = 1;
  26.         int p2 = 1, p3 = 1, p5 = 1;
  27.         // 丑数 x 2|3|5 也是丑数，因此算下前面的丑数分别乘以235后的数比对下，取最小值
  28.         // 对于取到的系数，后面再算丑数的时候基数就要以第二小的丑数为基数了
  29.         for (int i = 2; i <= n; i++) {
  30.             int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
  31.             dp[i] = Math.min(Math.min(num2, num3), num5);
  32.             if (dp[i] == num2) {
  33.                 p2++;
  34.             }
  35.             if (dp[i] == num3) {
  36.                 p3++;
  37.             }
  38.             if (dp[i] == num5) {
  39.                 p5++;
  40.             }
  41.         }
  42.         return dp[n];
  43.     }

96不同的二叉搜索树

  1. public int numTrees(int n) {
  2.         int[] dp = new int[n+1];
  3.         dp[0] = dp[1] = 1;
  4.         // n = i 时的二叉搜索树数量
  5.         for (int i = 2; i <= n; i++) {
  6.             // 在 1...i 的范围，每个j做root时，计算左右子树的数量
  7.             for (int j = 1; j <= i; j++) {
  8.                 dp[i] += (dp[j-1] * dp[i-j]);
  9.             }
  10.         }
  11.         return dp[n];
  12.     }
  14.     // n个节点能构成几个二叉搜索树
  15.     public int numTrees2(int n) {
  16.         if (n == 0 ||  n == 1){
  17.             return 1;
  18.         }
  19.         int count = 0;
  20.         for (int i = 1; i <= n; i++) {
  21.             // 以i为root，左边有i-1个节点
  22.             int left = numTrees(i-1);
  23.             // 右边有n-i个节点，这里只是计算构成搜索树的数量
  24.             // 因为右边的树的节点的值是i+1....n 构成的子树数量 == 1...n-i，所以直接按照n-i来算即可
  25.             int right = numTrees(n-i);
  26.             // 左右子树数量笛卡尔积作为最终组合树的数量
  27.             count += (left * right);
  28.         }
  29.         return count;
  30.     }

118杨辉三角

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

119杨辉三角II

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

70爬楼梯

  1. public int climbStairs(int n) {
  2.         int[] dp = new int[n+1];
  3.         dp[n] = 1;
  4.         for (int i = n-1; i >=0; i--) {
  5.             int v1 = dp[i+1];
  6.             int v2 = i+2 > n ? 0 : dp[i+2];
  7.             dp[i] = v1+v2;
  8.         }
  9.         return dp[0];
  10.     }
  12.     public int climbStairs2(int n) {
  13.         return run(n,0);
  14.     }
  16.     private int run(int n,int index){
  17.         if (index == n){
  18.             return 1;
  19.         }
  20.         if (index > n){
  21.             return 0;
  22.         }
  23.         int v1 = run(n,index+1);
  24.         int v2 = run(n,index+2);
  25.         return v1+v2;
  26.     }

322零钱兑换

  1. public int coinChange(int[] coins, int amount) {
  2.         if (amount <= 0) return 0;
  3.         int[] dp = new int[amount+1];
  4.         for (int i = 1; i <= amount; i++) {
  5.             int count = Integer.MAX_VALUE;
  6.             for (int coin : coins) {
  7.                 // 注意此时amount取值为i
  8.                 int index = i - coin;
  9.                 if (index >= 0 && dp[index] != Integer.MAX_VALUE){
  10.                     count = Math.min(count,dp[index]+1);
  11.                 }
  12.             }
  13.             dp[i] = count;
  14.         }
  15.         return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
  16.     }
  18.     public int coinChange2(int[] coins, int amount) {
  19.         int ans = run(coins,amount);
  20.         return ans == Integer.MAX_VALUE ? -1 : ans;
  21.     }
  23.     //要凑成amount数量需要的最少硬币数
  24.     private int run(int[] coins, int amount){
  25.         if (amount < 0){
  26.             return Integer.MAX_VALUE;
  27.         }
  28.         if(amount == 0){
  29.             return 0;
  30.         }
  31.         int count = Integer.MAX_VALUE;
  32.         for (int coin : coins) {
  33.             int res = run(coins,amount-coin);
  34.             if (res != Integer.MAX_VALUE){
  35.                 count = Math.min(count,1+res);
  36.             }
  37.         }
  38.         return count;
  39.     }

416分割等和子集

  1. public boolean canPartition(int[] nums) {
  2.         int n = nums.length;
  3.         if (n < 2) return false;
  4.         int sum = 0 , max = nums[0];
  5.         for (int num : nums) {
  6.             sum += num;
  7.             max = Math.max(max,num);
  8.         }
  9.         if ((sum & 1) == 1){
  10.             return false;
  11.         }
  12.         int half = sum/2;
  13.         if (max > half){
  14.             return false;
  15.         }
  16.         boolean[][] dp = new boolean[n][half+1];
  17.         for (int i = 0; i < n; i++) {
  18.             dp[i][0] = true;
  19.         }
  20.         dp[0][nums[0]] = true;
  21.         for (int i = 1; i < n; i++) {
  22.             int num = nums[i];
  23.             for (int j = 0; j <= half; j++) {
  24.                 if (j >= num){
  25.                     // 当前num选择或者不选择
  26.                     dp[i][j] = dp[i-1][j-num] | dp[i-1][j];
  27.                 }else {
  28.                     dp[i][j] = dp[i-1][j];
  29.                 }
  30.             }
  31.         }
  32.         return dp[n-1][half];
  33.     }
  35.     public boolean canPartition2(int[] nums) {
  36.         return run(nums,0,0,0);
  37.     }
  39.     // [index...n] 是否满足
  40.     private boolean run(int[] nums,int index,int lsum,int rsum){
  41.         if (index == nums.length){
  42.             return lsum == rsum;
  43.         }
  44.         boolean ans = false;
  45.         ans |= run(nums,index+1,lsum+nums[index],rsum);
  46.         if (ans) return true;
  47.         ans |= run(nums,index+1,lsum,rsum+nums[index]);
  48.         return ans;
  49.     }

931下降路径最小和

  1. public int minFallingPathSum(int[][] matrix) {
  2.         int row = matrix.length , col = matrix[0].length;
  3.         int[][] dp = new int[row][col];
  4.         for (int i = 0; i < col; i++) {
  5.             dp[row-1][i] = matrix[row-1][i];
  6.         }
  7.         for (int i = row-2; i >= 0; i--) {
  8.             for (int j = 0; j < col; j++) {
  9.                 int v1 = Integer.MAX_VALUE;
  10.                 if (j > 0){
  11.                     v1 = dp[i+1][j-1];
  12.                 }
  13.                 int v2 = dp[i+1][j];
  14.                 int v3 = Integer.MAX_VALUE;
  15.                 if (j < col-1){
  16.                     v3 = dp[i+1][j+1];
  17.                 }
  18.                 dp[i][j] =  matrix[i][j] + Math.min(Math.min(v1,v2),v3);
  19.             }
  20.         }
  21.         return Arrays.stream(dp[0]).min().getAsInt();
  22.     }
  24.     public int minFallingPathSum2(int[][] matrix) {
  25.         int ans = Integer.MAX_VALUE;
  26.         for (int i = 0; i < matrix.length; i++) {
  27.             ans = Math.min(ans,run(matrix,0,i));
  28.         }
  29.         return ans;
  30.     }
  32.     //[row...n]
  33.     private int run(int[][] matrix, int row, int column){
  34.         if (row == matrix.length){
  35.             return 0;
  36.         }
  37.         int v1 = Integer.MAX_VALUE;
  38.         if (column > 0){
  39.             v1 = run(matrix,row+1,column-1);
  40.         }
  41.         int v2 = run(matrix,row+1,column);
  42.         int v3 = Integer.MAX_VALUE;
  43.         if (column < matrix[0].length-1){
  44.             v3 = run(matrix,row+1,column+1);
  45.         }
  46.         return matrix[row][column] + Math.min(Math.min(v1,v2),v3);
  47.     }

120三角形最小路径和

  1. public int minimumTotal(List<List<Integer>> triangle) {
  2.         int n = triangle.size();
  3.         //只跟下一行的当前列和下一列有关，当前列的算好后，后面列的不会再用到当前列
  4.         int[] dp = new int[n];
  5.         for (int i = 0; i < n; i++) {
  6.             dp[i] = triangle.get(n-1).get(i);
  7.         }
  8.         for (int i = n-2; i >=0 ; i--) {
  9.             for (int j = 0; j <= i; j++) {
  10.                 int v1 = dp[j+1];
  11.                 int v2 = dp[j];
  12.                 dp[j] = triangle.get(i).get(j) + Math.min(v1,v2);
  13.             }
  14.         }
  15.         return dp[0];
  16.     }
  19.     public int minimumTotal1(List<List<Integer>> triangle) {
  20.         int n = triangle.size();
  21.         int[][] dp = new int[n][n];
  22.         for (int i = 0; i < n; i++) {
  23.             dp[n-1][i] = triangle.get(n-1).get(i);
  24.         }
  25.         for (int i = n-2; i >=0 ; i--) {
  26.             for (int j = 0; j <= i; j++) {
  27.                 int v1 = dp[i+1][j+1];
  28.                 int v2 = dp[i+1][j];
  29.                 dp[i][j] = triangle.get(i).get(j) + Math.min(v1,v2);
  30.             }
  31.         }
  32.         return dp[0][0];
  33.     }
  36.     public int minimumTotal2(List<List<Integer>> triangle) {
  37.         return run(triangle,0,0);
  38.     }
  41.     private int run(List<List<Integer>> triangle,int row,int col){
  42.         if (row == triangle.size()){
  43.             return 0;
  44.         }
  45.         int v1 = run(triangle,row+1,col+1);
  46.         int v2 = run(triangle,row+1,col);
  48.         return triangle.get(row).get(col) + Math.min(v1,v2);
  49.     }

62不同路径

  1. public int uniquePaths(int m, int n) {
  2.         int[][] dp = new int[m][n];
  3.         for (int i = 0; i < m; i++) {
  4.             dp[i][0] = 1;
  5.         }
  6.         for (int i = 0; i < n; i++) {
  7.             dp[0][i] = 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.         }
  15.         return dp[m-1][n-1];
  16.     }
  19.     public int uniquePaths2(int m, int n) {
  20.         return run(m,n,m-1,n-1);
  21.     }
  24.     // 到达tm,tn的不同路径数量
  25.     private int run(int m, int n,int tm,int tn){
  26.         if (tm == m || tn == n){
  27.             return 0;
  28.         }
  29.         if (tm == 0 || tn == 0){
  30.             return 1;
  31.         }
  32.         int ans = 0;
  33.         if (tm < m){
  34.             // 到达tm-1行的次数
  35.             ans += run(m,n,tm-1,tn);
  36.         }
  37.         if (tn < n){
  38.             // 到达tn-1列的次数
  39.             ans += run(m,n,tm,tn-1);
  40.         }
  41.         return ans;
  42.     }

63不同路径II

  1. public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  2.         int m = obstacleGrid.length;
  3.         int n = obstacleGrid[0].length;
  4.         int[][] dp = new int[m][n];
  5.         for (int i = 0; i < m; i++) {
  6.             if (obstacleGrid[i][0] == 1){
  7.                 break;
  8.             }
  9.             dp[i][0] = 1;
  10.         }
  11.         for (int i = 0; i < n; i++) {
  12.             if (obstacleGrid[0][i] == 1){
  13.                 break;
  14.             }
  15.             dp[0][i] = 1;
  16.         }
  18.         for (int i = 1; i < m; i++) {
  19.             for (int j = 1; j < n; j++) {
  20.                 dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j]+dp[i][j-1];
  21.             }
  22.         }
  23.         return dp[m-1][n-1];
  24.     }
  27.     public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
  28.         int m = obstacleGrid.length;
  29.         int n = obstacleGrid[0].length;
  30.         return run(obstacleGrid,m,n,m-1,n-1);
  31.     }
  33.     // 到达tm，tn
  34.     private int run(int[][] obstacleGrid,int m,int n,int tm,int tn){
  35.         if (tm == m || tn == n || obstacleGrid[tm][tn] == 1){
  36.             return 0;
  37.         }
  38.         if (tm == 0 || tn == 0){
  39.             return 1;
  40.         }
  41.         int ans = 0;
  42.         if (tm < m){
  43.             ans += run(obstacleGrid,m,n,tm-1,tn);
  44.         }
  45.         if (tn < n){
  46.             ans += run(obstacleGrid,m,n,tm,tn-1);
  47.         }
  48.         return ans;
  49.     }

64最小路径和

  1. public int minPathSum(int[][] grid) {
  2.         int m = grid.length,n = grid[0].length;
  3.         int[][]dp = new int[m][n];
  4.         dp[0][0] = grid[0][0];
  5.         for (int i = 1; i < m; i++) {
  6.             dp[i][0] = dp[i-1][0]+grid[i][0];
  7.         }
  8.         for (int i = 1; i < n; i++) {
  9.             dp[0][i] = dp[0][i-1]+grid[0][i];
  10.         }
  11.         for (int i = 1; i < m; i++) {
  12.             for (int j = 1; j < n; j++) {
  13.                 dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
  14.             }
  15.         }
  16.         return dp[m-1][n-1];
  17.     }
  19.     public int minPathSum2(int[][] grid) {
  20.         int m = grid.length,n = grid[0].length;
  21.         return run(grid,m,n,m-1,n-1);
  22.     }
  24.     private int run(int[][] grid,int m,int n,int tm,int tn){
  25.         if (tm < 0 || tn < 0 ){
  26.             return Integer.MAX_VALUE;
  27.         }
  28.         if (tm == 0 && tn == 0){
  29.             return grid[0][0];
  30.         }
  31.         int v1 = run(grid,m,n,tm-1,tn);
  32.         int v2 = run(grid,m,n,tm,tn-1);
  33.         int ans = grid[tm][tn];
  34.         return ans + Math.min(v1,v2);
  35.     }

221最大正方形

  1. public int maximalSquare(char[][] matrix) {
  2.         int m = matrix.length,n = matrix[0].length;
  3.         // i,j处 1组成的正方形的连续长度
  4.         // 取相邻三个位置的长度最小值+1
  5.         // 边界处最多为1
  6.         int[][] dp = new int[m][n];
  7.         int max = 0;
  8.         // 边界
  9.         for (int i = 0; i < m; i++) {
  10.             if (matrix[i][0] == '1'){
  11.                 dp[i][0] = 1;
  12.                 max = 1;
  13.             }
  14.         }
  15.         for (int i = 0; i < n; i++) {
  16.             if (matrix[0][i] == '1'){
  17.                 dp[0][i] = 1;
  18.                 max = 1;
  19.             }
  20.         }
  21.         for (int i = 1; i < m; i++) {
  22.             for (int j = 1; j < n; j++) {
  23.                 if (matrix[i][j] == '1'){
  24.                     dp[i][j] = 1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
  25.                 }
  26.                 max = Math.max(max,dp[i][j]);
  27.             }
  28.         }
  29.         return max*max;
  30.     }

5最长回文串

516最长回文子序列

  1. public int longestPalindromeSubseq(String s) {
  2.         int[][] dp = new int[s.length()][s.length()];
  3.         for (int l = 0; l < dp.length; l++) {
  4.             for (int r = 0; r < dp.length; r++) {
  5.                 if (l == r){
  6.                     dp[l][r] = 1;
  7.                 }
  8.                 if (l == r-1){
  9.                     dp[l][r] = s.charAt(l) == s.charAt(r) ? 2 : 1;
  10.                 }
  11.             }
  12.         }
  13.         for (int l = s.length()-3; l >=0; l--) {
  14.             for (int r = 2+l; r <s.length(); r++) {
  15.                 // 一共四种情况
  16.                 // 一定不以l人作为左右两端
  17.                 int v1 = dp[l+1][r-1];
  18.                 // 一定不以l做左端点，但可能以r为右端点
  19.                 int v2 = dp[l+1][r];
  20.                 // 一定不以r做右端点，但可能以l为左端点
  21.                 int v3 = dp[l][r-1];
  22.                 // 一定以lr为端点，判断相等序列长度+2并判断不以lr为端点情况，否则直接0
  23.                 int v4 = s.charAt(l) == s.charAt(r) ? 2 + v1 : 0;
  24.                 dp[l][r] = Math.max(Math.max(v1,v2),Math.max(v3,v4));
  25.             }
  26.         }
  28.         return dp[0][s.length()-1];
  29.     }
  32.     // str在[l...r]范围内的最长回文子序列长度
  33.     private int run(char[] str,int l,int r){
  34.         if (l == r){
  35.             return 1;
  36.         }
  37.         if (l == r-1){
  38.             return str[l] == str[r] ? 2 : 1;
  39.         }
  40.         // 一共四种情况
  41.         // 一定不以l人作为左右两端
  42.         int v1 = run(str,l+1,r-1);
  43.         // 一定不以l做左端点，但可能以r为右端点
  44.         int v2 = run(str,l+1,r);
  45.         // 一定不以r做右端点，但可能以l为左端点
  46.         int v3 = run(str,l,r-1);
  47.         // 一定以lr为端点，判断相等序列长度+2并判断不以lr为端点情况，否则直接0
  48.         int v4 = str[l] == str[r] ? 2 + v1 : 0;
  49.         return Math.max(Math.max(v1,v2),Math.max(v3,v4));
  50.     }

300最长递增子序列

  1. public int lengthOfLIS(int[] nums) {
  2.         int n = nums.length;
  3.         int[] dp = new int[n];
  4.         Arrays.fill(dp,1);
  5.         for (int i = 1; i < n; i++) {
  6.             for (int j = 0; j < i; j++) {
  7.                 if (nums[i] > nums[j]){
  8.                     dp[i] = Math.max(dp[i],dp[j]+1);
  9.                 }
  10.             }
  11.         }
  12.         return Arrays.stream(dp).max().getAsInt();
  13.     }
  15.     public int lengthOfLIS2(int[] nums) {
  16.         return run(nums,nums.length-1);
  17.     }
  19.     // index 处和 0..index-1处的一个个的比较，如果更大就+1，得出index处最大的长度
  20.     private int run(int[] nums,int index){
  21.         if (index == 0){
  22.             return 1;
  23.         }
  24.         int cur = nums[index];
  25.         int ans = 1;
  26.         for (int i = 0; i < index; i++) {
  27.             if (cur > nums[i]){
  28.                 int next = run(nums,i);
  29.                 ans = Math.max(ans,next+1);
  30.             }
  31.         }
  32.         return ans;
  33.     }

376摆动序列

  1. public int wiggleMaxLength(int[] nums) {
  2.         int n = nums.length;
  3.         if (n < 2) {
  4.             return n;
  5.         }
  6.         int[] up = new int[n];
  7.         int[] down = new int[n];
  8.         up[0] = down[0] = 1;
  9.         for (int i = 1; i < n; i++) {
  10.             if (nums[i] > nums[i - 1]) {
  11.                 up[i] = Math.max(up[i - 1], down[i - 1] + 1);
  12.                 down[i] = down[i - 1];
  13.             } else if (nums[i] < nums[i - 1]) {
  14.                 up[i] = up[i - 1];
  15.                 down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
  16.             } else {
  17.                 up[i] = up[i - 1];
  18.                 down[i] = down[i - 1];
  19.             }
  20.         }
  21.         return Math.max(up[n - 1], down[n - 1]);
  22.     }

image.png
image.png