【算法】算法模板

算法模板

---

---

简介

博主在LeetCode网站中学习算法的过程中使用到并总结的算法模板，在算法方面算是刚过初学者阶段，竞赛分数仅2000。

为了节省读者的宝贵时间，部分基础的算法与模板未列出。当然也并非全面。

文章及代码存在不正不明之处还望指正。

数组

• 生成数组测试数据
• 区间合并
• 前缀和 二维前缀和 差分数组
• 二分查找(各种开闭区间组合)
• 回溯 子集型(选或不选/选哪个) 组合型 排列

    class ArrTemplates {class Generator {public void generateArr(int n, int max) {Random r = new Random();int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = r.nextInt(max);}System.out.println(Arrays.toString(arr));}public void generateArr(int m, int n, int max) {Random r = new Random();int[][] arr = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {arr[i][j] = r.nextInt(max);}}for (int[] ints : arr) {System.out.println(Arrays.toString(ints));}}}/*** 区间*/class Interval {/*** 区间合并*/List<int[]> intervalMerge(int[][] ranges) {int n = ranges.length;Arrays.sort(ranges, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);List<int[]> rList = new ArrayList<>(n);int[] r1 = ranges[0];for (int i = 1; i < n; i++) {int[] r2 = ranges[i];if (r2[0] <= r1[1]) {r1[1] = Math.max(r1[1], r2[1]);} else {rList.add(r1);r1 = r2;}}rList.add(r1);return rList;}}class PrefixSum {/*** 前缀和*/public int[] getPreFix(int[] arr) {int n = arr.length;int[] pre = new int[n + 1];for (int i = 0; i < n; i++) {pre[i + 1] = pre[i] + arr[i];}return pre;}/*** 二维前缀和*/public int[][] getPrefix(int[][] matrix) {int m = matrix.length, n = matrix[0].length;int[][] pre = new int[m + 1][n + 1];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + matrix[i][j];}}return pre;}/*** 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和*/public int query(int[][] pre, int r1, int c1, int r2, int c2) {return pre[r2 + 1][c2 + 1] - pre[r2 + 1][c1] - pre[r1][c2 + 1] + pre[r1][c1];}//差分数组public int[] getDiff(int n, int[] arr) {int[] diff = new int[n];diff[0] = arr[0];for (int i = 1; i < n; i++) {diff[i] = arr[i] - arr[i - 1];}
//            for (int i = 1; i < n; i++) {
//                diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
//            }return diff;}int[] getDiff(int n, int[][] arr) {int[] diff = new int[n]; // 差分数组for (int[] q : arr) {int l = q[0], r = q[1], x = q[2];diff[l] += x;if (r + 1 < n) {diff[r + 1] -= x;}}for (int i = 1; i < n; i++) {diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a}return diff;}}class BinarySearch {/*** 二分查找* 闭区间* 循环不变量:左侧小于等于目标值,右侧大于目标值* r-1<=target,l+1>target*/int binarySearch(int[] nums, int target) {int l = 0, r = nums.length - 1;while (l <= r) {int m = l + (r - l) / 2;if (nums[m] < target) {l = m + 1;} else {r = m - 1;}}return l;}/*** 左闭右开区间[l,r)* [l,mid) [mid+1,r)*/int binarySearch2(int[] nums, int target) {int l = 0, r = nums.length;while (l < r) {int m = l + (r - l) / 2;if (nums[m] < target) {l = m + 1;} else {r = m;}}return l;}/*** 左开右闭区间(l,r]* (l,mid-1] (mid,r]*/int binarySearch3(int[] nums, int target) {int l = -1, r = nums.length - 1;while (l < r) {int m = l + (r - l) / 2;if (nums[m] < target) {l = m;} else {r = m - 1;}}return l;}/*** 开区间(l,r)* (l,mid)(mid,r)*/int binarySearch4(int[] nums, int target) {int l = -1, r = nums.length;while (l + 1 < r) {int m = l + (r - l) / 2;if (nums[m] < target) {l = m;} else {r = m;}}return r;}}class Backtrack {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();int n;boolean[] visited = new boolean[n];/*** 子集型* 选或不选 n*2^n*/void backtrack(int[] nums, int idx) {//解if (idx == n) {res.add(new ArrayList<>(path));}//尝试 选或不选//不选backtrack(nums, idx + 1);//选path.add(nums[idx]);backtrack(nums, idx + 1);//回溯path.remove(path.size() - 1);}/*** 子集型* 每次选一个*/void backtrack2(int[] nums, int idx) {//解res.add(new ArrayList<>(path));if (idx == n) {return;}for (int i = idx; i < n; i++) {path.add(nums[i]);backtrack2(nums, i + 1);//回溯path.remove(path.size() - 1);}}/*** 组合型* 逆序排列*/void backtrack(int[] nums, int idx, int k) {//剩余不足达到k个if (idx < k - path.size()) {return;}if (path.size() == k) {res.add(new ArrayList<>(path));return;}for (int i = idx; i >= 0; i--) {path.add(nums[i]);backtrack(nums, i - 1, k);//回溯path.remove(path.size() - 1);}}/*** 组合型* 正序排列*/void backtrack2(int[] nums, int idx, int k) {if (n - idx < k - path.size()) {return;}if (path.size() == k) {res.add(new ArrayList<>(path));return;}for (int i = idx; i < n; i++) {path.add(nums[i]);backtrack2(nums, i + 1, k);//回溯path.remove(path.size() - 1);}}/*** 排列* Tn*n!*/void backtrack3(int[] nums, int idx) {if (idx == n) {res.add(new ArrayList<>(path));return;}for (int i = 0; i < n; i++) {if (!visited[i]) {visited[i] = true;path.add(nums[i]);backtrack3(nums, idx + 1);visited[i] = false;path.remove(path.size() - 1);}}}}}

字符串

• kmp字符串匹配
• 子串
• 回文串

class StringTemplates {/*** kmp*/public int kmpSearchIndex(String source, String target) {int n = source.length(), m = target.length();if (m == 0) {return 0;}// 创建部分匹配表int[] kmp = new int[m];for (int i = 1, j = 0; i < m; i++) {// 字符不匹配时，j回溯到上一个匹配的字符，继续匹配while (j > 0 && target.charAt(i) != target.charAt(j)) {j = kmp[j - 1];}// 当haystack和needle的字符匹配时，将j的值加一if (target.charAt(i) == target.charAt(j)) {j++;}// 更新部分匹配表kmp[i] = j;}// 在haystack中查找needlefor (int i = 0, j = 0; i < n; i++) {// 字符不匹 j回溯到上一个匹配的字符while (j > 0 && source.charAt(i) != target.charAt(j)) {j = kmp[j - 1];}// 字符匹配时，已匹配字符数+1if (source.charAt(i) == target.charAt(j)) {j++;}//找到needleif (j == m) {return i - m + 1;}}// 没有找到needle，则返回-1return -1;}/*** 获取长度为len的所有子串*/private String[] getSubstrings(String s, int len) {int n = s.length();String[] substrings = new String[n - len + 1];for (int j = 0; j <= n - len; j++) {substrings[j] = s.substring(j, j + len);}return substrings;}/*** 是否回文串*/boolean isPalindrome(String str) {int left = 0, right = str.length() - 1;while (left < right) {if (str.charAt(left) != str.charAt(right)) {return false;}left++;right--;}return true;}/*** 是否回文串*/private boolean isPalindrome(char[] ss, int l, int r) {if (l == r) {return true;}while (l < r) {if (ss[l++] != ss[r--]) {return false;}}return true;}/*** 字符串任意子串是否回文串*/boolean[][] palindrome(char[] cs) {int n = cs.length;boolean[][] p = new boolean[n][n];//1
//            for (int i = 0; i < n; i++) {
//                Arrays.fill(p[i], true);
//            }
//            for (int i = n - 1; i >= 0; i--) {
//                for (int j = i + 1; j < n; ++j) {
//                    p[i][j] = cs[i] == cs[j] && p[i + 1][j - 1];
//                }
//            }//2for (int len = 1; len <= n; len++) {//从i开始,统计长度为len的子串是否为回文串for (int i = 0; i <= n - len; i++) {int j = i + len - 1;if (len == 1) {p[i][j] = true;} else if (len == 2) {p[i][j] = cs[i] == cs[j];} else {// 大于两个字符时，判断首尾字符是否相等，并且去除首尾字符后的子串是否是回文串p[i][j] = cs[i] == cs[j] && p[i + 1][j - 1];}}}return p;}}

列表

• 翻转
• 快慢指针

    class ListTemplates {/*** 翻转链表*/public void reverse(ListNode head, ListNode tail) {ListNode last = null;ListNode curr = head;ListNode end = tail.next;while (curr != end) {//下一个节点ListNode next = curr.next;//将当前节点的指针指向前一个节点curr.next = last;//将当前节点置位下一个节点的前置last = curr;//循环控制curr = next;}}/*** 快慢指针*/boolean fast_slowPoints(ListNode head) {ListNode slow = head;ListNode fast = head;while (slow != null && fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}}

数学

• 最大/小值
• lcm
• gcd
• 快速幂
• lowbit
• 质数/素数(埃氏筛)
• 回文数
• 组合数

    class MathTemplates {/*** min*/public int min(int a, int... b) {for (int i : b) {a = Math.min(a, i);}return a;}/*** max*/public int max(int a, int... b) {for (int i : b) {a = Math.max(a, i);}return a;}/*** 最小公倍数 Lowest Common Multiple*/private long lcm(long a, long b) {return a * b / gcd(a, b);}/*** 最大公约数 Greatest common divisor*/public long gcd(long x, long y) {return y == 0 ? x : gcd(y, x % y);}/*** 快速幂*/public double fastPow(double x, long n) {double res = 1.0;while (n > 0) {if (n % 2 == 1) {res *= x;}x *= x;n /= 2;}return res;}/*** 快速幂*/public long fastPow(long x, long n) {long res = 1;while (n > 0) {if (n % 2 == 1) {res *= x;}x *= x;n /= 2;}return res;}public int lowbit(int i) {//x & (~x + 1);return i & -i;}/*** 二进制1个数* Integer.bitCount(i)*/public int bitCount(int i) {i = i - ((i >>> 1) & 0x55555555);i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);i = (i + (i >>> 4)) & 0x0f0f0f0f;i = i + (i >>> 8);i = i + (i >>> 16);return i & 0x3f;}/*** 是否质数*/private boolean isPrime(int n) {for (int i = 2; i * i <= n; i++) {if (n % i == 0) {return false;}}return true;}private boolean isPrime2(int n) {// 小于等于1的整数不是素数if (n <= 1) {return false;}// 2和3是素数if (n <= 3) {return true;}// 如果整数能被2或3整除，不是素数if (n % 2 == 0 || n % 3 == 0) {return false;}// 除了2和3，素数都可以表示成6的倍数加1或减1的形式(在6的倍数两侧的数不是素数)for (int i = 5; i * i <= n; i += 6) {if (n % i == 0 || n % (i + 2) == 0) {return false;}}return true;}boolean[] isPrime;/*** 质数表-埃氏筛* Tnlog(logn) Sn*/private void getPrimes(int n) {isPrime = new boolean[n];Arrays.fill(isPrime, true);isPrime[1] = false;for (int i = 2; i <= Math.sqrt(n); i++) {if (isPrime[i]) {// 将 i 的所有倍数标记为非质数(合数)for (int j = i * i; j < n; j += i) {isPrime[j] = false;}}}}/*** 回文数*/public boolean isPalindrome(int x) {if (x < 0 || x % 10 == 0 && x != 0) {return false;}int reverse = 0;while (x > reverse) {reverse = reverse * 10 + x % 10;x /= 10;}return x == reverse || x == reverse / 10;}private final int N = 31;private final int[][] c = new int[N][N];{for (int i = 0; i < N; i++) {c[i][0] = c[i][i] = 1;for (int j = 1; j < i; j++) {//Cn,k = Cn-1,k-1 + Cn-1,kc[i][j] = c[i - 1][j - 1] + c[i - 1][j];}}}/*** 计算n个数里拿k个数的组合数*/public long comb(int n, int k) {long ans = 1;for (int i = 1; i <= k; i++) {ans *= (n - k + i);ans /= i;}return ans;}}

树

• 树状数组

    class TreeTemplates {/*** 树状数组*/class BinaryIndexedTrees {private int[] tree;private int[] nums;/*** TOnlogn*/public BinaryIndexedTrees(int[] nums) {//lowbit(0)计算为0;舍弃0下标;this.tree = new int[nums.length + 1];this.nums = nums;for (int i = 0; i < nums.length; i++) {add(i + 1, nums[i]);}}/*** TOlogn*/public void update(int index, int val) {add(index + 1, val - nums[index]);nums[index] = val;}/*** TOlogn*/public int sumRange(int left, int right) {return prefixSum(right + 1) - prefixSum(left);}/*** 用于计算树状数组的 x节点的父节点* x的父节点索引= x+=lowbit(x)* lowbit(x) 未 非负整数x在二进制下的最低为1及其后面的0构成的数(x的除最后一位1外,其他位置0)*/private int lowBit(int x) {//return x & (~x + 1);return x & -x;}private void add(int index, int val) {while (index < tree.length) {tree[index] += val;index += lowBit(index);}}private int prefixSum(int index) {int sum = 0;while (index > 0) {sum += tree[index];index -= lowBit(index);}return sum;}}}

图

• 无向图/带权图 领接矩阵/表
• 并查集
• Dijkstra
• Floyd

    class GraphTemplates {/*** 无向图*/public List<Integer>[] edgesToGraph(int n, int[][] edges) {List<Integer>[] graph = new List[n];Arrays.setAll(graph, i -> new ArrayList<>());for (int[] edge : edges) {int x = edge[0];int y = edge[1];graph[x].add(y);graph[y].add(x);}return graph;}/*** 带权图*/public List<int[]>[] edgesToWGraph(int n, int[][] edges) {List<int[]>[] wgraph = new List[n];Arrays.setAll(wgraph, i -> new ArrayList<>());for (int[] edge : edges) {int x = edge[0];int y = edge[1];int w = edge[2];wgraph[x].add(new int[]{y, w});wgraph[y].add(new int[]{x, w});}return wgraph;}/*** 带权领接矩阵*/public int[][] edgesToWGraph2(int n, int[][] edges) {int INF = Integer.MAX_VALUE / 2;int[][] graph = new int[n][n];for (int i = 0; i < n; i++) {Arrays.fill(graph[i], INF);}for (int[] edge : edges) {graph[edge[0]][edge[1]] = edge[2];}return graph;}/*** 并查集*/class UnionFind {int[] fa;public UnionFind(int n) {fa = new int[n];for (int i = 0; i < n; i++) {fa[i] = i;}}public int find(int x) {if (fa[x] == x) {return x;}return fa[x] = find(fa[x]);}boolean union(int x, int y) {int fx = find(x), fy = find(y);if (fx == fy) {return false;}if (fx > fy) {fa[fy] = fx;} else {fa[fx] = fy;}return true;}}/*** 长度统计 联通分量统计 高度压缩 并查集*/class UnionFind2 {//父节点int[] fa;//高度int[] rk;//子集长度int[] sz;//连通分量数int count;public UnionFind2(int n) {fa = new int[n];rk = new int[n];sz = new int[n];for (int i = 0; i < n; i++) {fa[i] = i;sz[i] = 1;}count = n;}public int find(int x) {if (fa[x] == x) {return x;}return fa[x] = find(fa[x]);}boolean union(int x, int y) {int fx = find(x), fy = find(y);if (fx == fy) {return false;}//如果 x的高度大于 y，则令 y的上级为 xif (rk[fx] > rk[fy]) {fa[fy] = fx;sz[fx] += sz[fy];} else {//如果 x的高度和 y的高度相同，则令 y的高度加1if (rk[fx] == rk[fy]) {rk[fy]++;}fa[fx] = fy;sz[fy] += sz[fx];}count--;return true;}public boolean isSame(int x, int y) {return find(x) == find(y);}public int size(int x) {return sz[find(x)];}public int count() {return count;}}class Dijkstra {/*** dijkstra 统计单源最短路径长度*/public long dijkstraCalculateLenOfShortestPaths(int n, int[][] edges, int start, int end) {List<int[]>[] wgraph = edgesToWGraph(n, edges);//最短路径长度,最短路径次数long[] dist = new long[n];Arrays.fill(dist, Long.MAX_VALUE);dist[start] = 0;PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));//节点,权重pq.offer(new long[]{start, 0});while (!pq.isEmpty()) {long[] node = pq.poll();int u = (int) node[0];//s到达u的最短路径权重long suw = node[1];//此路径不是到达u的最短路径if (suw > dist[u]) {continue;}for (int[] edge : wgraph[u]) {int v = edge[0], uvw = edge[1];//s到达v的最短路径权重long svw = dist[v];if (suw + uvw < svw) {dist[v] = suw + uvw;pq.offer(new long[]{v, dist[v]});}}}return dist[end];}/*** dijkstra 统计单源最短路径数量*/public int dijkstraCalculateCount0fShortestPaths(int n, int[][] edges, int start, int end) {List<int[]>[] wgraph = edgesToWGraph(n, edges);//最短路径长度,最短路径次数long[] dist = new long[n];Arrays.fill(dist, Long.MAX_VALUE);dist[start] = 0;int[] counts = new int[n];counts[start] = 1;PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));//节点,权重pq.offer(new long[]{start, 0});while (!pq.isEmpty()) {long[] node = pq.poll();int u = (int) node[0];//s到达u的最短路径权重long suw = node[1];//此路径不是到达u的最短路径if (suw > dist[u]) {continue;}for (int[] edge : wgraph[u]) {int v = edge[0], uvw = edge[1];//s到达v的最短路径权重long svw = dist[v];//s到达u的最短路径数量int suc = counts[u];if (suw + uvw < svw) {dist[v] = suw + uvw;counts[v] = suc;pq.offer(new long[]{v, dist[v]});} else if (suw + uvw == svw) {counts[v] = (counts[v] + suc) % 1000000007;}}}return counts[end];}/*** dijkstra 单元 统计最短路径长度与数量*/public long[][] dijkstraCalculateLenAndCount0fShortestPaths(int n, int[][] edges) {List<int[]>[] wgraph = edgesToWGraph(n, edges);//最短路径长度,最短路径次数long[][] dist = new long[n][2];Arrays.setAll(dist, i -> new long[]{Long.MAX_VALUE, 0});dist[0] = new long[]{0, 1};PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));//节点,权重pq.offer(new long[]{0, 0});while (!pq.isEmpty()) {long[] node = pq.poll();int u = (int) node[0];//s到达u的最短路径权重long suw = node[1];//此路径不是到达u的最短路径if (suw > dist[u][0]) {continue;}for (int[] edge : wgraph[u]) {int v = edge[0], uvw = edge[1];//s到达v的最短路径权重long svw = dist[v][0];//s到达u的最短路径数量long suc = dist[u][1];if (suw + uvw < svw) {dist[v][0] = suw + uvw;dist[v][1] = suc;pq.offer(new long[]{v, dist[v][0]});} else if (suw + uvw == svw) {dist[v][1] = (dist[v][1] + suc) % 1000000007;}}}return dist;}/*** 稠密图 邻接矩阵*/public int[] dijkstra(int n, int[][] edges, int start) {int INF = Integer.MAX_VALUE / 2;int[][] graph = new int[n][n];int[] dist = new int[n];for (int i = 0; i < n; i++) {Arrays.fill(graph[i], INF);dist[i] = INF;}for (int[] edge : edges) {graph[edge[0]][edge[1]] = edge[2];}boolean[] vis = new boolean[n];dist[start] = 0;for (int i = 0; i < n; i++) {// 找到当前距离最小的未访问节点int x = -1;for (int y = 0; y < n; ++y) {if (!vis[y] && (x == -1 || dist[y] < dist[x])) {x = y;}}// 访问标记vis[x] = true;for (int y = 0; y < n; ++y) {// 更新最短路长度dist[y] = Math.min(dist[y], dist[x] + graph[x][y]);}}return dist;}}//多源最短路径class Floyd {public int[][] floyd(int n, int[][] edges) {int INF = Integer.MAX_VALUE;int[][] dist = new int[n][n];for (int i = 0; i < n; ++i) {Arrays.fill(dist[i], INF);dist[i][i] = 0;}for (int[] e : edges) {dist[e[0]][e[1]] = e[2];}for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] == INF || dist[k][j] == INF) {continue;}dist[i][j] = Math.max(dist[i][j], dist[i][k] + dist[k][j]);}}}return dist;}}class Prim {public void primMST(int n, int[][] edges) {}}}

动态规划

• 爬楼梯
• 打家劫舍
• 子数组
• 子序列
• 背白 01背包 完全背包
• 划分
• 区间

    class DpTemplates {/*** 入门* 爬楼梯 打家劫舍*/class Base {/*** 爬楼梯-每次相同方式二选一*/public int climbingStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];/*int p1 = 0, p2 = 1;for (int i = 1; i <= n; i++) {p2 += p1;p1 = p2 - p1;}return p2;*/}/*** 花费代价爬楼梯 每次相同方式二选一,并选择较少消费*/public int climbingStairsByMinCost(int[] cost) {int len = cost.length;for (int i = 2; i < len; i++) {cost[i] = Math.min(cost[i - 1], cost[i - 2]) + cost[i];}return Math.min(cost[len - 1], cost[len - 2]);}/*** 打家劫舍 根据要求选或不选*/public int rob(int[] nums) {int[] dp = new int[2];for (int num : nums) {//选 上一个只能是不选int doit = dp[1] + num;//不选 上一个选或不选int not = Math.max(dp[0], dp[1]);dp[0] = doit;dp[1] = not;}return Math.max(dp[0], dp[1]);}}/*** 子数组dp*/class Subarray {/*** 子数组最大值*/public int maxSubArrayDp(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int res = nums[0];for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);res = Math.max(res, dp[i]);}return res;}/*** 子数组最大值*/public int maxSubArray(int[] nums) {int max = nums[0];int pre = max;for (int i = 1; i < nums.length; i++) {pre = Math.max(pre + nums[i], nums[i]);max = Math.max(max, pre);}return max;}/*** 单调递增/减 最长子数组*/public int longestMonotonicSubarray(int[] nums) {int res = 1;int i = 0, n = nums.length;while (i < n - 1) {//相等直接跳过if (nums[i + 1] == nums[i]) {i++;continue;}// 记录开始位置int start = i;//定下基调：递增/递减boolean inc = nums[i + 1] > nums[i];// i 和 i+1 已经满足要求，从 i+2 开始判断i += 2;while (i < n && nums[i] != nums[i - 1] && (nums[i] > nums[i - 1]) == inc) {i++;}// 从 start 到 i-1 是满足题目要求的（并且无法再延长的）子数组res = Math.max(res, i - start);i--;}return res;}}/*** 子序列dp*/class Subsequence {/*** 最长公共子序列LCS*/public int longestCommonSubsequence(int[] arr1, int[] arr2) {int m = arr1.length, n = arr2.length;int[][] dp = new int[m + 1][n + 1];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dp[i + 1][j + 1] = arr1[i] == arr2[j] ? dp[i][j] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);}}return dp[m][n];}/*** 子序列数量*/public int diffSubsequenceCount(int[] arr1, int[] arr2) {int MOD = 1_000_000_007;int m = arr1.length;int n = arr2.length;int[][] dp = new int[m + 1][n + 1];//initfor (int i = 0; i <= m; i++) {dp[i][0] = 1;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= i && j <= n; j++) {dp[i][j] = dp[i - 1][j];if (arr1[i - 1] == arr2[j - 1]) {dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;}}}return dp[m][n];}/*** 最长递增子序列 LIS*/public int longestIncreasingSubsequence(int[] nums) {int n = nums.length;int[] dp = new int[n];int res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}res = Math.max(res, dp[i]);}return res + 1;}}/*** 背包dp*/class Knapsack {/*** 01背包*/public int zeroOneKnapsack(int[] ws, int[] vs, int c) {int n = ws.length;int[][] dp = new int[n + 1][c + 1];dp[0][0] = 1;// 动态规划求解for (int i = 1; i <= n; i++) {for (int j = 1; j <= c; j++) {if (ws[i - 1] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - ws[i - 1]] + vs[i - 1]);}}}return dp[n][c];}/*** 完全背包*/public int completeKnapsack(int[] ws, int[] vs, int c) {int n = ws.length;int[][] dp = new int[n + 1][c + 1];dp[0][0] = 1;// 动态规划求解for (int i = 1; i <= n; i++) {for (int j = 1; j <= c; j++) {if (ws[i - 1] > j) {// 物品 i 不被选入背包dp[i][j] = dp[i - 1][j];} else {// 物品 i 被选入背包// 可以重复选取，所以是 dp[i][j - weights[i - 1]] + values[i - 1]dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - ws[i - 1]] + vs[i - 1]);}}}return dp[n][c];}}/*** 划分dp*/class Partition {/*** 能否划分* f[i] 表示 a[:i]能否划分;* 枚举最右侧划分左端l,判断a[l,i]是否符合条件* f[i] = min/max(f[i],f[l-1]+1)*/boolean canPartition(int[] nums) {int n = nums.length;boolean[] dp = new boolean[n + 1];dp[0] = true;for (int i = 1; i <= n; i++) {for (int l = 0; l <= i; l++) {if (dp[l] && check(nums, l, i)) {//num[l:i] 是否符合条件dp[i] = true;break;}}}return dp[n];}/*** 划分个数  f[i] 表示a[:i]在约束下 能划分的最大/小个数* 枚举右侧划分左端l,判断a[l,i]是否符合条件* f[i] = min/max(f[i],f[l-1]+1)*/int partitionNum(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];for (int i = 0; i < n; i++) {dp[i + 1] = dp[i] + 1;for (int l = 0; l <= i; l++) {//符合划分条件if (check(nums, l, i)) {//min / maxdp[i + 1] = Math.min(dp[i + 1], dp[l] + 1);}}}return dp[n];}/*** 约束划分数量  划分为k个,计算最优解;* f[i][j]: 将a[:i]划分为j个部分的最优解;* 枚举右侧左端l,从f[l][j-1]转移到f[i][j],考虑最最优解的影响*/public int partitionCnt(int[] nums, int k) {int n = nums.length;int[] pre = new int[n + 1];for (int i = 0; i < n; i++) {pre[i + 1] = pre[i] + nums[i];}int[][] dp = new int[n + 1][k + 1];for (int i = 0; i <= n; i++) {Arrays.fill(dp[i], Integer.MAX_VALUE);}dp[0][0] = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= Math.min(i, k); j++) {for (int l = j - 1; l < i; l++) {//最小化 划分子数组的和dp[i][j] = Math.min(dp[i][j], Math.max(dp[l][j - 1], pre[i] - pre[l]));}}}return dp[n][k];}/*** 约束划分长度 子数组长度<=k时,最大和* f[i] 表示nums[:i] 划分后,子数组最大值* 枚举最后子数组左端点l* f[i] = f[r]+val*/public int partitionLen(int[] nums, int k) {int n = nums.length;int[] dp = new int[n + 1];for (int i = 1; i <= n; i++) {//逆序维护区间最大值int max = 0;for (int l = i - 1; l >= i - k && l >= 0; l--) {max = Math.max(max, nums[l]);dp[i] = Math.max(dp[i], dp[l] + max * (i - l));}}return dp[n];}private boolean check(int[] nums, int l, int r) {return true;}/*** 区间不相交划分 限定区间范围(1~n)或 [is[0],is[1]]区间范围较小*/public long intervalPartition(int n, int[][] is) {//按区间结束排序List<int[]>[] list = new List[n + 1];for (int[] interval : is) {if (list[interval[1]] == null) {list[interval[1]] = new ArrayList<>();}list[interval[1]].add(new int[]{interval[0], interval[1] - interval[0] + interval[2]});}//dpi 表示 到达第i个点时,能获得的最大价值long[] dp = new long[n + 1];for (int i = 1; i <= n; i++) {dp[i] = dp[i - 1];if (list[i] == null) {continue;}for (int[] r : list[i]) {dp[i] = Math.max(dp[i], dp[r[0]] + r[1]);}}return dp[n];}/*** 区间不相交划分  [is[0],is[1]]区间范围较大时*/public int intervalPartition(int[][] is) {int n = is.length;//按区间排序Arrays.sort(is, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);//dpi: 在i项中 能获得的最大价值int[] dp = new int[n + 1];for (int i = 0; i < n; i++) {int s = is[i][0], p = is[i][2];//二分找到上一个区间int l = 0, r = i - 1;while (l <= r) {int m = l + (r - l) / 2;//可无缝衔接<=,否则<if (is[m][1] <= s) {l = m + 1;} else {r = m - 1;}}dp[i + 1] = Math.max(dp[i], dp[r + 1] + p);}return dp[n];}}}