扎气球最高分，本题是2021年11月27日举办的第13届蓝桥杯青少组Python编程选拔赛真题编程部分第5题。题目要求对于给定的n个排成一排的气球，将所有气球扎破能够得到的最高分数。
先来看看题目的要求吧。
编程实现：
小明去游乐场玩飞镖扎气球的游戏，一共有n个气球，依次排成一行，每个气球上有一个数字，表示这个气球的分值。
游戏计分规则：
1、戳破1个气球，将获得其本身及左右相邻气球，共三个分值相乘的分数；
2、如果戳破的气球左边或右边没有气球，则获得其本身及相邻气球，共两个分值相乘的分数；如果被戳破的气球左边和右边都没有气球（是最后一个被戳破的气球），则这个气球本身的分值作为分数；
3、已经被戳破的气球不再计算。
飞镖数量不限，可以任意选择顺序戳破气球，根据计分规则，争取使得游戏最后得分最高。
例如：一共有3个气球，分值分别为2，4，6。
若想获得最高得分：
1). 先戳破4，得分为2 x 4 x 6 = 48；
2). 再戳破2，得分为2 x 6 = 12，累计得分60；
3). 再戳破6，得分为6，累计得分66；
最后总得分为66，为最高得分。
输入描述：
输入n个正整数，表示气球的分值，且正整数之间以一个英文逗号隔开
输出描述：
输出正整数，表示戳破所有气球后获得的最高得分
样例输入：
2,4,6
样例输出：
66
这是一道动态规划算法题，涉及的知识点包括循环、列表和动态规划等。
定义dp数组 初始状态 状态转移方程 遍历顺序
dp[0][1] = dp[1][2] = dp[2][3] = dp[3][4] = dp[4][5]= 0dp[0][5]= dp[0][1] + dp[1][5] + 3dp[0][5]= dp[0][2] + dp[2][5] + 2dp[0][5]= dp[0][3] + dp[3][5] + 4这相当于把dp[0][5]拆分成两个子区间，分别是dp[0][4]和dp[4][5]，戳破当前气球的得分为1 * 6 * 1，所以：
dp[0][5]= dp[0][4] + dp[4][5] + 6dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] + p[i] * p[j] * p[k])
dp[2][5] = dp[2][3] + dp[3][5] + p[2]* p[3] * p[5]dp[2][5] = dp[2][4] + dp[4][5] + p[2]* p[4] * p[5]思路有了，接下来，我们就进入具体的编程实现环节。
代码不多，说明4点：
1). pts表示输入的气球分值，左右各增加了一个分值为1的气球，这里直接使用列表相加的运算，非常方便；
2). 二维dp列表行和列都是n + 2，初始值为0，这里使用了列表推导式；
3). i表示行，从下到上，初始值是n -1，终点是0，j表示列，自左至右，初始值是i + 1，终点是n + 1；
4). k表示分割点，起始值是k+1，终点是j - 1。
至此，整个程序就全部完成了，你可以输入不同的数据来测试效果啦。
循环语句，尤其是嵌套循环；
列表的操作；
动态规划算法；
作为本次测评的最后一题，代码虽然不多，但是难度较大。关键点有两个，一是理解区间DP的算法思想，二是彻底弄清填充DP表格的方法和过程。
估计你已经发现了，最终的代码并不多，难的是过程分析，动态规划说难也难，说简单也简单。
动态规划说白了，就是根据题目意思定义一个表格，可能是一维的，也可能是二维的，然后找到规律，也就是状态转移方程，不断地计算并填充每一个单元格。
因此，在学习动态规划算法的时候，一定要亲自动手绘制并填充表格，这个过程会有些繁琐，但是效果非常好，写代码反倒是最简单的事情了。
超平老师给你留两道思考题：
1). 如何使用递归算法，计算最大分值？
2). 如果使用斜线遍历的顺序，代码又该怎么写呢？
你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。
需要源码的，可以添加本人微信。
另外，超平老师创建了一个蓝桥杯备考交流群，这是专门为老师和家长打造的免费社群，您可以与来自全国各地的老师、家长共同交流经验，分享学习心得。
超平老师也会给大家带来及时的赛事动态，备考攻略，真题资源分享，帮助各位更好地备考第15届蓝桥杯赛事，力争取得优异的成绩。
扫码或长按加入微信群
