前置知识: 讲解066、067、068、069 - 动态规划基础 讲解067 - 最长公共子序列长度，本节课题目1需要 讲解069 - 多维费用背包及其空间压缩技巧，本节课题目4需要 讲解072 - 最长递增子序列，本节课题目3需要 讲解080、081 - 状压dp，本节课题目2需要 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

很多动态规划题目要求返回的答案不是一个简单数值，而是一个具体的方案 1，利用动态规划表生成决策路径，本节课题目1、题目2、题目3 2，有时候需要增加额外的路径收集结构，本节课题目4

对这一类的题目来说，动态规划是最重要的，得到具体方案只是一个比较简单的处理技巧

题目1 最长公共子序列其中一个结果 给定两个字符串str1和str2 输出两个字符串的最长公共子序列 如果最长公共子序列为空，则输出-1 测试链接 : https://www.nowcoder.com/practice/4727c06b9ee9446cab2e859b4bb86bb8

题目2 最小的必要团队 作为项目经理，你规划了一份需求的技能清单req_skills 并打算从备选人员名单people中选出些人组成必要团队 编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表 所谓必要团队，就是在这个团队中 对于所需求的技能列表req_skills中列出的每项技能，团队中至少有一名成员已经掌握 请你返回规模最小的必要团队，团队成员用人员编号表示 你可以按 任意顺序 返回答案，题目数据保证答案存在 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/

题目3 最长递增子序列字典序最小的结果 给定数组arr，设长度为n 输出arr的最长递增子序列 如果有多个答案，请输出其中字典序最小的 注意这道题的字典序设定（根据提交的结果推论的）： 每个数字看作是单独的字符，比如120认为比36的字典序大 保证从左到右每个数字尽量小 测试链接 : https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927 测试链接 : https://www.luogu.com.cn/problem/T386911

题目4 潜水的最大时间与方案 一共有n个工具，每个工具都有自己的重量a、阻力b、提升的停留时间c 因为背包有限，所以只能背重量不超过m的工具 因为力气有限，所以只能背阻力不超过v的工具 希望能在水下停留的时间最久 返回最久的停留时间和下标字典序最小的选择工具的方案 注意这道题的字典序设定（根据提交的结果推论的）： 下标方案整体构成的字符串保证字典序最小 比如下标方案"1 120"比下标方案"1 2"字典序小 测试链接 : https://www.luogu.com.cn/problem/P1759

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