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

区间dp：大范围的问题拆分成若干小范围的问题来求解

可能性展开的常见方式： 1）基于两侧端点讨论的可能性展开 2）基于范围上划分点的可能性展开

区间dp专题分为上、下两期，一共12个题 本节课 区间dp-上 会安排6个题，熟悉区间dp的可能性展开

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

题目1 让字符串成为回文串的最少插入次数 给你一个字符串 s 每一次操作你都可以在字符串的任意位置插入任意字符 请你返回让s成为回文串的最少操作次数 测试链接 : https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

注意： 本题有关空间压缩的实现，可以参考讲解067，题目4，最长回文子序列问题的讲解 这两个题空间压缩写法高度相似 因为之前的课多次讲过空间压缩的内容，所以这里不再赘述

题目2 预测赢家 给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏 玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手 开始时，两个玩家的初始分值都是 0 每一回合，玩家从数组的任意一端取一个数字 取到的数字将会从数组中移除，数组长度减1 玩家选中的数字将会加到他的得分上 当数组中没有剩余数字可取时游戏结束 如果玩家 1 能成为赢家，返回 true 如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 你可以假设每个玩家的玩法都会使他的分数最大化 测试链接 : https://leetcode.cn/problems/predict-the-winner/

题目3 多边形三角剖分的最低得分 你有一个凸的 n 边形，其每个顶点都有一个整数值 给定一个整数数组values，其中values[i]是第i个顶点的值(顺时针顺序) 假设将多边形 剖分 为 n - 2 个三角形 对于每个三角形，该三角形的值是顶点标记的乘积 三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和 返回 多边形进行三角剖分后可以得到的最低分 测试链接 : https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/

题目4 切棍子的最小成本 有一根长度为n个单位的木棍，棍上从0到n标记了若干位置 给你一个整数数组cuts，其中cuts[i]表示你需要将棍子切开的位置 你可以按顺序完成切割，也可以根据需要更改切割的顺序 每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和 对棍子进行切割将会把一根木棍分成两根较小的木棍 这两根木棍的长度和就是切割前木棍的长度 返回切棍子的最小总成本 测试链接 : https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/

题目5 戳气球 有 n 个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中 现在要求你戳破所有的气球。戳破第 i 个气球 你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号 如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球 求所能获得硬币的最大数量 测试链接 : https://leetcode.cn/problems/burst-balloons/

题目6 布尔运算 给定一个布尔表达式和一个期望的布尔结果 result 布尔表达式由 0 (false)、1 (true)、& (AND)、 | (OR) 和 ^ (XOR) 符号组成 布尔表达式一定是正确的，不需要检查有效性 但是其中没有任何括号来表示优先级 你可以随意添加括号来改变逻辑优先级 目的是让表达式能够最终得出result的结果 返回最终得出result有多少种不同的逻辑计算顺序 测试链接 : https://leetcode.cn/problems/boolean-evaluation-lcci/

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