前置知识: 讲解067、讲解068 - 从递归入手二维动态规划 & 空间压缩技巧 讲解076 - 区间dp-上 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

区间dp：大范围的问题拆分成若干小范围的问题来求解 可能性展开的常见方式： 1）基于两侧端点讨论的可能性展开 2）基于范围上划分点的可能性展开

区间dp专题分为上、下两期，一共12个题 本节课 区间dp-下 再安排6个题，继续见识更多的区间dp题目

注意：尤其是 讲解067 - 从递归入手二维动态规划，整个套路请务必掌握！

题目1 完成配对需要的最少字符数量 给定一个由'['、']'、'('，')'组成的字符串 请问最少插入多少个括号就能使这个字符串的所有括号正确配对 例如当前串是 “([[])”，那么插入一个’]’即可满足 输出最少需要插入多少个字符 测试链接 : https://www.nowcoder.com/practice/e391767d80d942d29e6095a935a5b96b

题目2 涂色 & 奇怪打印机 假设你有一条长度为5的木板，初始时没有涂过任何颜色 你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色 用一个长度为5的字符串表示这个目标：RGBGR 每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色 例如第一次把木板涂成RRRRR 第二次涂成RGGGR 第三次涂成RGBGR，达到目标 返回尽量少的涂色次数 测试链接 : https://www.luogu.com.cn/problem/P4170 测试链接 : https://leetcode.cn/problems/strange-printer/

题目3 合唱队 具体描述情打开链接查看 测试链接 : https://www.luogu.com.cn/problem/P3205

题目4 移除盒子 给出一些不同颜色的盒子boxes，盒子的颜色由不同的正数表示 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止 每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1） 这样一轮之后你将得到 k * k 个积分 返回你能获得的最大积分总和 测试链接 : https://leetcode.cn/problems/remove-boxes/

题目5 合并石头的最低成本 有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头 每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数 返回把所有石头合并成一堆的最低成本 如果无法合并成一堆返回-1 测试链接 : https://leetcode.cn/problems/minimum-cost-to-merge-stones/

题目6 统计不同回文子序列 给你一个字符串s，返回s中不同的非空回文子序列个数 由于答案可能很大，请你将答案对10^9+7取余后返回 测试链接 : https://leetcode.cn/problems/count-different-palindromic-subsequences/

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