【題目描述】
Given n balloons, indexed from 0 ton-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
有n個氣球舀寓，編號為0到n-1，每個氣球都有一個分?jǐn)?shù)，存在nums數(shù)組中。每次吹氣球i可以得到的分?jǐn)?shù)為nums[left] * nums[i] * nums[right]焚刺，left和right分別表示i氣球相鄰的兩個氣球。當(dāng)i氣球被吹爆后，其左右兩氣球即為相鄰温学。要求吹爆所有氣球，得到最多的分?jǐn)?shù)氧腰。
【題目鏈接】
www.lintcode.com/en/problem/burst-balloons/
【題目解析】
考慮分治法來處理的時候枫浙，如果選擇以某個氣球為分割點，那么其左邊部分和右邊部分都要依賴與那個氣球古拴，因此我們不能讓這個氣球先爆．也就是說我們選擇分割點的時候不是選擇先爆的氣球箩帚，而是最后爆的氣球，這樣分成的左右兩個部分將相互獨立．即如果最后只剩下氣球i黄痪，那么其最后只依賴與第０和ｎ－１個氣球紧帕，而在[0, i] 和 [i, n-1]兩個區(qū)間是相互獨立的。
這樣我們就可以將問題分割為相互獨立的子集．這樣時間復(fù)雜為O(n^n). 但是在枚舉各個分割點的時候會有很多重復(fù)的計算桅打，因此我們可以保存已經(jīng)計算過的區(qū)間．這樣時間復(fù)雜度可以優(yōu)化到O(n^3).
【參考答案】
