筆試算法模拟題精解之“神奇的棋子”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好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月份比賽正式開啟！機械鍵盤等你拿！