数据结构优化dp 其它优化dp 3181. 执行操作可获得的最大总奖励 II

网格图dp 在网格图上的移动 62. 不同路径 1594. 矩阵的最大非负积

背包 0-1背包 给定一个背包的容量c和n个物品，第i个物品的体积为w[i]，价值为v[i]。每个物品选或不选，求体积和不超过capacity时的最大价值和 核心思路：枚举第i个物品选或不选 初始化一个二维数组dp，其中dp[i][j]表示在考虑前i个物品、背包容量为j的情况下的最大总价值 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) 背包至多装capacity 求方案数 求最大价值和（传统01背包） 背包恰好装capacity 求方案数: 494. 目标和 求最大价值和 求最小价值和 背包最少装capacity 求方案数 求最小价值和 其它 3180. 执行操作可获得的最大总奖励 I 完全背包 给定一个背包的容量c和n种物品，第i种物品的体积为w[i]，价值为v[i]。每种物品无限次重复选，求体积和不超过capacity时的最大价值和 考虑第i个物品选不选时，可以重复选择，所以这里考虑dp[i][c]时，可能多次更新dp[i][c-w[i]] + v[i] dp[i][c] = max(dp[i-1] ...

哈希大法 枚举右，维护左 对于双变量问题，例如两数之和 (a_i + a_j = t)，可以枚举右边的 (a_j)，转换成单变量问题。也就是在 (a_j) 左边查找是否有 (a_i = t - a_j)，这可以用哈希表维护。 用哈希记录之前的数，并用于判断情况是否成立 1. 两数之和：经典的枚举右，维护左 421. 数组中两个数的最大异或值: 对于每一位bit，枚举右，维护左 二重哈希 第一个哈希的value被当作key放入第二个哈希 3092. 最高频率的 ID 字符串哈希 请看字符串哈希 前缀和+哈希表 请看前缀和 遍历过程维护集合大小 在遍历的过程中，我们可以通过前后双指针（滑动窗口），动态维护一个哈希表，来确保当前窗口的元素集合大小不超过某个值k，如下代码所示 12345678910111213for (int i = 0, j = 0; i < n; i++) { // 前后双指针+哈希表记录集合大小 for (; j < n && map.size() <= k; j++) { if (ma ...

最近公共祖先 描述 问题就是寻找树上两个节点的最近公共祖先节点 边权重均等查询 此题难度超过2500 现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。 另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [ai, bi] 。对于每条查询，请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。 注意： 查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。 从 ai 到 bi的路径是一个由 不同 节点组成的序列，从节点 ai 开始，到节点 bi 结束，且序列中相邻的两个节点在树中共享一条边。 返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。 示例 1： 1234567输 ...

循环节 循环节：指在序列中出现的一种重复的、周期性的模式。这个模式可以是一组连续的元素，也可以是整个序列的重复。 周期性特征：序列中的循环节反映了序列的周期性特征，即序列中的某一段会以某种方式重复出现。 寻找循环节的方法 快慢指针法：用两个指针，一个每次走一步，另一个每次走两步。如果存在循环节，两个指针最终会相遇。 哈希表法：使用哈希表记录每次遍历的状态，如果发现某个状态已经出现过，说明存在循环节。 统计重复个数 定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。 例如，str == ["abc", 3] =="abcabcabc" 。 如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。 例如，根据定义，s1 = "abc" 可以从 s2 = "ab***dbe***c" 获得，仅需要删除加粗且用斜体标识的字符。 现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = ...

差分数组 1234a[0] a[1] a[2] a[3] a[4] (0)差分数组: a[0] a[1]-a[0] a[2]-a[1] a[3]-a[2] a[4]-a[3] (-a[4])对差分数组求前缀和: a[0] a[1] a[2] a[3] a[4] (0)// 考虑末尾0(-a[4])，那么差分数组之和sum=0 前缀和就是离散版本的“求积分”，差分数组就是离散版本的“求微分” 形成目标数组的子数组最少增加次数 给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。 请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则： 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。 答案保证在 32 位有符号整数以内。 示例 1： 1234567输入：target = [1,2,3,2,1]输出：3解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。[0,0,0,0,0] 将下标为 0 到 4 的元素（包 ...

前缀和 前缀和是一种数组变换方法，通过将数组中每个元素替换为从数组起始位置到当前位置的所有元素之和。这样，计算任意区间的和变得非常高效，只需一次前缀和计算即可，而不需要多次重复计算。 123int[] nums;int n = nums.length, sum[] = new int[n+1];sum[i+1] = sum[i] + nums[i]; 需要用sum[0]表示空数组的和 l到r的区间和表示为 sum[r+1] - sum[l] 例如，nums[0]到nums[5]的区间和表示为 sum[6] - sum[0] 二维前缀和 定义sum[i+1][j+1]表示左上角grid[0][0]，右下角grid[i][j]的子矩阵元素和 123456int[][] sum = new int[m + 1][n + 1];for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] ...

单调栈 单调栈(Monotonic Stack)是一种特殊的栈，它首先是一个栈，其次栈中的所有元素单调递增或者单调递减 上下界 单调栈在算法中的应用在于它能够在一次扫描(从左到右)即O(n)的复杂度之内找到数组中每一个元素的后上界(单增栈)或者后下界(单减栈) 2866. 美丽塔 II(2072) 1944. 队列中可以看到的人数(2105) 双单调栈 2454. 下一个更大元素 IV(2175) 单调队列 从「维护单调性」的角度上来说，单调队列和单调栈是一样的。在单调栈的基础上，单调队列多了一个「移除队首」的操作，这类似滑动窗口移动左指针 left 的过程。所以从某种程度上来说，单调队列 = 单调栈 + 滑动窗口。 滑动窗口最值问题 239. 滑动窗口最大值 2944. 购买水果需要的最少金币数(1709)

二维偏序 概念 偏序关系满足： 反自反性（Reflexivity）： 对于集合中的每个元素，关系都与自身存在。 反对称性（Antisymmetry）： 如果存在a<=b && b<=a，则必须是a==b 传递性（Transitivity）： 如果存在a<=b && b<=c，则必须是a<=c 二维偏序问题涉及对一个二维数据集中元素的排序，其中排序不仅仅依赖于元素自身的大小关系，还可能依赖于元素在不同维度上的关系。 二维偏序是这样一类问题：已知点对的序列(a1,b1), (a2,b2), (a3,b3)...， 并在其上定义某种偏序关系<，现有点(ai,bi)，求满足(aj,bj) < (ai,bi)的的数量。 二维偏序问题一般是要使其中的一个维度有序，再通过树状数组的方式处理另一个维度 翻转对 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 示例 1: 12输入: ...