前置知识: 讲解066 ~ 讲解081 - 动态规划基础 讲解082 - 动态规划中用观察优化枚举的技巧-上 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

上节课讲了利用严格位置依赖的动态规划来 建立空间感，进而观察并优化枚举 本节课继续讲述 观察并优化转移方程 来优化枚举（题目1、2） 同时还要讲述 观察并设计高效的查询结构 来优化枚举（题目3、4）

注意： 优化枚举的技巧很多，讲解075-多重背包利用二进制分组、单调队列进行优化，本节课讲根据观察优化 【必备】课程中的优化手段是笔试、面试最常见的优化类型，此外动态规划的枚举行为还有如下的优化： 单调栈、树状数组、线段树、预处理表、状态设计优化、单调性优化、斜率优化、四边形不等式 ..等等 这些内容会在【扩展】、【挺难】课程里安排讲述

题目1 规划兼职工作 你打算利用空闲时间来做兼职工作赚些零花钱，这里有n份兼职工作 每份工作预计从startTime[i]开始、endTime[i]结束，报酬为profit[i] 返回可以获得的最大报酬 注意，时间上出现重叠的 2 份工作不能同时进行 如果你选择的工作在时间X结束，那么你可以立刻进行在时间X开始的下一份工作 测试链接 : https://leetcode.cn/problems/maximum-profit-in-job-scheduling/

利用观察单调性 + 二分搜索的方式优化枚举，最优解时间复杂度O(n*logn)

题目2 K个逆序对数组 逆序对的定义如下： 对于数组nums的第i个和第j个元素 如果满足0<=i<jnums[j]，则为一个逆序对 给你两个整数n和k，找出所有包含从1到n的数字 且恰好拥有k个逆序对的不同的数组的个数 由于答案可能很大，只需要返回对10^9+7取余的结果 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/

最优解 利用观察 + 构造窗口累加和，已经进入 观察并设计高效的查询结构 的范畴了 只不过这个结构就仅存在于概念，并用一个int类型的变量维护而已

题目3 自由之路 题目描述比较多，打开链接查看 测试链接 : https://leetcode.cn/problems/freedom-trail/

优化枚举的核心是贪心策略： 下一步做枚举时，不需要枚举所有可能性，只需要枚举 顺时针的最近、逆时针的最近 两种可能性即可

贪心当然会有专题讲述！【必备】课程的动态规划专题结束了，就会开始贪心的专题

题目4 累加和不大于k的最长子数组 给定一个无序数组arr，长度为n，其中元素可能是正、负、0 给定一个整数k，求arr所有的子数组中累加和<=k的最长子数组长度 测试链接 : https://www.nowcoder.com/practice/3473e545d6924077a4f7cbc850408ade

强烈推荐先看一下讲解046

利用构造单调数组 + 二分搜索的解不是最优解，时间复杂度O(n*logn)

最优解中包含的贪心思想（窗口的加速建立、可能性的淘汰），是这个题的重点，时间复杂度O(n)

贪心当然会有专题讲述！【必备】课程的动态规划专题结束了，就会开始贪心的专题

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com