Category: Algorithm

The Knapsack problem is the “Hello World” of Dynamic Programming. But beyond the basic 0/1 version lies a world of clever optimizations and mathematical tricks. In this post, we’ll break down the three major types and the patterns that solve them. 1. The Foundation: 0/1 Knapsack The Rule: You have one of each item. You…

题目描述 给出一组包含 m 个不等式，有 n 个未知数的形如： 的不等式组，求任意一组满足这个不等式组的解。 解答 差分约束问题的核心是将不等式转化为图论中的边，然后通过求单源最短路来求解： 求解最短路时，要求能够判断负环，使用 Bellman-Ford 或 SPFA 算法。 Bellman-Ford 初始化：先给所有节点的 “当前最短路径”（dist[i]） 赋值为 “无穷大”，只有源点的最短路径设为 0（自己到自己距离为 0）。 多轮松弛更新： 检测负权回路： SPFA Bellman-Ford算法的优化。 Bellman-Ford 效率低的关键是 “每轮遍历所有边”，但实际上：只有某个节点的最短路径被更新后，以这个节点为起点的边，才有可能更新它的邻接节点的最短路径。 SPFA 就是抓住这个特点，用 “队列” 记录 “刚刚被更新过最短路径的节点”，只处理这些节点的出边，避免遍历无用的边。 AC代码

题目描述 在一条大路一旁有许多栋楼，每栋楼里有许多小学生。所以唯恐世界不乱的牛A打算在路上任选几点（可以和楼重合，当然也可以不重合）建立小学，且使所有小学生上学走的路程之和最短。牛A发现修建一所小学根本无法满足他唯恐世界不乱的心理，所以他准备建立K所小学。 输入格式 第一行2个整数，表示楼数n，学校数k（1<=n,k<=100） 第二行n个整数，表示每栋楼的学生数（0＜每栋楼学生数≤100 ) 第三行n-1个数，分别表示楼i到楼i+1之间距离（1≤距离≤100，1≤i≤n-1） 输出格式 即学生走的距离和的最小值 解答 使用动态规划。“选 k 个点求最小代价”→ 想到找最优子结构→DP 定义DP状态：f[i][j]表示 “前 i 栋楼建 j 所小学的最小总路程” 则答案即为f[n-1][k] (从第0栋开始) 状态转移：考虑区间[0,i]内最后一所学校覆盖的范围，当覆盖的范围为[t+1,i]时， cost[i][j]表示[i,j]区间有一所学校时的最小总路程。(子问题，关键！) 预处理cost数组 区间确定时，显然学校应建在一处使得： 据此计算cost数组每一项，复杂度都为O(n)O(n) AC代码

题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 解答 第一问：求数列的最长不上升子序列长度 第二问：求最少的不上升子序列覆盖数 根据 Dilworth 定理，最少的不上升子序列覆盖数等于 最长上升子序列 (Longest Increasing Subsequence, LIS) 的长度，因此两个问题可以相互转化。 先说算法： 第二问比较容易用贪心的思路来理解： 将dp数组的值看成目前用过的所有导弹高度的上限，按顺序遍历所有目标， 打完以后将导弹的高度上限改为这个目标的高度。正好，无论对已有的导弹还是新增的导弹，更新为新的目标的高度后均能保持数组仍然单调递增，为运用二分查找提供了条件。 Dilworth 定理暗示着第一问也能使用类似的方法，但不如第二问直观。读者可尝试自行解释。我的一种解释是：将此时的 dp 数组看作所求的最长单调子序列的变体， 这样，dp 第 i 位表示长度为 i 时，最后一个元素的上限。 AC代码 相关题