易函123

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

题目描述 给定序列 X={x1,xn},序列 Z{z1,zn},是 X 的子序列是指存在一个严格递增下标序列{i1,ik}使得对于所有 j=1,..k 有 zj = xij 例如 Z={B,C,D,B}是序列 X={A,B,C,D,B,A}的子序列，想要的递增下标序列为{2,3,5,7} 穷举法 找出 X 字符所有可能的子序列 2^n 对于 x 的每一个子序列，判断其是否是 Y 的一个子序列，需要的时间为 m 求的总时长 (2^n) * m 动态规划最优值当 X 有 i 个元素，Y 有 j 个元素，最长公共子序列的长度 lij 12345lij = { 0 i=0 或者j=0 （边界条件） l(i-1,j-1)+1 i>0，j>0, and Xi = Yj max{l[i-1,j],l[i,j-1]} i>0,j>0,and Xi≠Yj} 自底向上计算最优值

题目描述 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 自底向上求最优解

题目描述 给定 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) ...

题目描述 给定一个数组 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;} 自底向上求解最优值

基本性质 和分治相似 动态规划也是将原问题分解成子问题求解 和分治不同 不是通过分治的递归方式，而是自底向上的求解问题 机器人问题分治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 规模问题 找出最优解对应的最优值，并递归定义最优值 以自底而上的方式计算出最优值 根据计算最优值时得到的信息，构造最优解

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

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

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

基本思想 规模较大的问题分解为规模较少的问题，较小的问题分解成更小的问题，直到容易解决为止 对较小问题解决，是继续分解————递归方程 直到容易解决为止(通常一个元素)，边界条件 可以无限变小直到自己会做为止。 分治步骤 分解：将原问题分解成规模较小的子问题 原问题可以被分为多个子问题 P1,P2,…,PK 子问题形式需要和原问题一致 解决：通过递归的方式解决子问题 P1,P2 独立解，以及 P1,P2 共同相关的解 合并，对子问题的解进行合并，形成原问题的解。 快速排序分解选择一个主元素 k，将原数组分解为两个子数组，小于主元素的所有元素组成了一个子数组，大于主元素的所有元素组成了另外一个子数组。[<=k] [>k] 解决对子数组进行递归调用解决 合并通过上述步骤，对已完成原数组的排序，无需合并操作