易函123

状态压缩动态规划 集合状态压缩 用二进制表示集合，之后使用整型表示二进制，如旅行商问题的 TP 数组 空间状态压缩 自底向上的方法求解最优值过程中，压缩最优值的存储空间

基本性质 和分治相似 动态规划也是将原问题分解成子问题求解 和分治不同 不是通过分治的递归方式，而是自底向上的求解问题 机器人问题分治12345path(i,j) = { 0, i=0,j=0; 1, i=0,j不等于0 或者i不等于0，j=0; path(i-1,j)+path(i,j-1), 其他} 动态规划适应场景 子问题并不独立，即子问题是可能重复的 主要用于优化问题（求最优解），且问题具有最优子结构性质 最优子结构性质 最优子结构性质指原问题的最优解一定包含了子问题的最优解 最短路径问题，具有最优子结构性质 基本步骤 定义子问题，并分析最优解的结构特征 分治通常是将原问题对半分，而动态规划是将 n 规模问题分解成 n-1 规模问题 找出最优解对应的最优值，并递归定义最优值 以自底而上的方式计算出最优值 根据计算最优值时得到的信息，构造最优解

题目描述 G = (V,E) 是一个带权重的完全图，顶点个数|v| = n(顶点代表城市 c)，每条边 eij∈E 赋予权重 dij 代表从顶点 ci 到顶点 cj 的距离或者费用。令 π 对对所有顶点的任一排列（排列代表访问城市序列），f（π）为排列的总长度（或）费用，则旅行商问题求 从第一个城市到第 n 个城市，再从第 n 个城市回来 旅行商问题的最优解结构特征 最优解子结构性质 子问题重叠如以下路径 c1c2c3c4….cn 和 c1c3c2c4….cn 都有子问题 c4….cn 旅行商问题最优解对应的最优值，并递归定义最优值min TSP(c1，C/ci,cj)+dji 得出递归方程 1234567TSP(c1，C/ci,cj)= { d(c1,cj) |c|=1,i≠1 min TSP(c1，C/ci,cj)+dji 其他}TSP* = TSP(c1，C/ci,cj) +dj1 自底向上求最优解

题目描述 给定一个数组 A，找出此数组中，所有子数组中和最大的子数组，即为最大子数组问题。 动态规划逻辑 n-1 为原问题 n 的子问题 求解改为：包含数组最后一个元素的最大子数组 最大子数组问题的最优解的结构特征B[n] = B[n-a]Uxn 找出最优解对应的最优值，并递归的定义最优值 1234b[n] = { b[n-1] + xn b[n-1]>0; xn b[n-1]<=0;} 自底向上求解最优值

题目描述 给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包容量为 C（也就是背包的总承重 C）。问，应如何选择装入背包的物品，使得背包的物品的总价值 V 最大化 分析分析 0-1 背包问题最优解的结构特征 一种情况是第 n 个物品不包含在背包中设 x* = （x1,x2,x3,…,xn-1,xn）则（x1,x2,x3,…,xn-1）必为第 n-1 个物品（剔除第 n 个物品），且背包容易为 C 情况下的最优解 第二种情况是 n 个物品包含在背包中则（x1,x2,x3,…,xn-1）必为第 n-1 个物品，在背包容量为 C-wn 情况下的最优解 找出 0-1 背包问题最优解对应的最优值，并递归定义最优值在 n 个物品中，背包容量为 C 情况下总价值，用 m(n,C)表示最优值 12345m(n,C) = { 0, n=0或C=0 max{m(n-1,C), m(n-1,C-wn)+vn} wn<C m(n-1,C) ...

问题描述 给定屏幕上的点对 S，|S|=n,每个点可用坐标（x，y）表示，若 p∈S，q∈S，p≠q,则 pq 称为一个点对，则 d(p,q)称为该点对的欧几里得距离。我们要求得所有点对的最小值 dmin

题目描述 在一个 2^k×2^k 个方格组成的棋盘上，存在一个特殊的方格，这个特殊方格不能被覆盖，要求用四种 L 型骨牌覆盖出特殊方格外的整个棋盘。任意两个 L 型骨牌不能重叠。 二维的需要在 x,y 上对半分 制造特殊格子

题目描述 给定一个无序数组 S = [s1,s2,…sk,…sn],输出数组的第 k 小元素，也就是从小到大，第 k 小元素。 分解 如何将原数组分成两个子问题 寻找一个中间元素 如何找到这个处于中间位置的元素 m 将 n 个元素分成 m 个组（通常每组 5 个元素），取每组的中间元素，再去这些中间元素的中间元素 怎么找到中间元素的中间元素。 递归调用 分为所有小于 m 数组 + 等于 m +大于 m 的所有数组

题目描述 给定一个数组 A，找出此数组中，所有子数组中和最大的子数组，即为最大子数组问题。 基本步骤分解对原数组进行二分，也就是将数组划分为左右相等（或者相差一个元素）的两个子数组。 合并对半分的时候需要注意，中间重合部分的。原数组，左边数组+右边数组+中间 合并而成。求三个值的最大解即可 max{subLMax,subRMax,subMMax} 横跨在两个子问题上的最大子数组 只要一次遍历左右数组的所有子数组，即可找到横跨在两个子问题上的最大子数组 复杂度

题目地址https://leetcode.cn/problems/group-anagrams/ 题目描述123456789101112131415161718给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]示例 2:输入: strs = [""]输出: [[""]]示例 3:输入: strs = ["a"]输出: [["a"]] 解答123456789101112cons ...