江西做企业网站的公司wordpress缓存首页不正常

当前位置： 首页 > news >正文

江西做企业网站的公司,wordpress缓存首页不正常,手机网站开发周期,上海建设局网站 招聘算法模板 文章目录 算法模板简介数组字符串列表数学树图动态规划 简介 博主在LeetCode网站中学习算法的过程中使用到并总结的算法模板#xff0c;在算法方面算是刚过初学者阶段#xff0c;竞赛分数仅2000。 为了节省读者的宝贵时间#xff0c;部分基础的算法与模板未列出。…算法模板 文章目录 算法模板简介数组字符串列表数学树图动态规划 简介 博主在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 {/** 区间合并/Listint[] intervalMerge(int[][] ranges) {int n ranges.length;Arrays.sort(ranges, (a, b) - a[0] b[0] ? a[1] - b[1] : a[0] - b[0]);Listint[] 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-1target,l1target/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) [mid1,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 {ListListInteger res new ArrayList();ListInteger path new ArrayList();int n;boolean[] visited new boolean[n];/** 子集型* 选或不选 n2^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);}}/** 排列* Tnn!/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;}}数学 最大/小值lcmgcd快速幂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的父节点索引 xlowbit(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;}}}图 无向图/带权图 领接矩阵/表并查集DijkstraFloyd class GraphTemplates {/** 无向图/public ListInteger[] edgesToGraph(int n, int[][] edges) {ListInteger[] 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 Listint[][] edgesToWGraph(int n, int[][] edges) {Listint[][] 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) {Listint[][] wgraph edgesToWGraph(n, edges);//最短路径长度,最短路径次数long[] dist new long[n];Arrays.fill(dist, Long.MAX_VALUE);dist[start] 0;PriorityQueuelong[] 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) {Listint[][] 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;PriorityQueuelong[] 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) {countsv % 1000000007;}}}return counts[end];}/** dijkstra 单元 统计最短路径长度与数量/public long[][] dijkstraCalculateLenAndCount0fShortestPaths(int n, int[][] edges) {Listint[][] 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};PriorityQueuelong[] 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 % 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 (!visy) {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 和 i1 已经满足要求从 i2 开始判断i 2;while (i n nums[i] ! numsi - 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 % 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) {//按区间结束排序Listint[][] 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];}}}