【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“105.神奇的棋子”的解法探究。先来看一下题目内容：

题目详情

等级：中等
知识点：搜索
查看题目：神奇的棋子

Tom有一天在玩棋子，这些棋子都不是普通的棋子。现在有n个棋子排成一排(2<=n<=18)，每个棋子都有它们自己的权值ai(0<=ai<=1e9)，现在Tom每次选择连续的三枚棋子，然后中间的那枚棋子会消失，而它左右两边的棋子会分别加上它的权值，问最后只剩下两枚棋子的时候，这两枚棋子的权值的最小的和为多少？
输入棋子个数n和一个数组a，a[i]表示每个棋子的权值。
输出一个数，表示最终剩下的两枚棋子的权值的最小的和。

示例1
输入：
4
[1,2,3,4]
输出：
17

解题思路描述

因为我们每选择一次，消失的数对左右都有影响，而且也会被挑选的顺序影响，所以需要去考虑每个棋子的贡献。

枚举一段区间最后选的棋子，然后将其分为两段区间，设该段区间的左端点最终的贡献为x，右端点最终的贡献为y，那么在只剩最后选的数，左端点，右端点三个点时，我们选择最后的那个点，那么最后那个数最终的贡献就是x+y次了，然后根据这个思路已知分治下取就好了。

dfs(l, r, x, y)表示左端点、右端点、左端点的贡献、右端点的贡献的区间合并成两个数的最小和。
时间复杂度最坏是O(n^3*2^n)。

看完之后是不是有了答题思路了呢，快来练练手吧：105.神奇的棋子

在线编程周赛、月赛火热进行中，更有限时答题活动，社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！