前往
大廳
主題

[leetcode]312. Burst Balloons

♙♲⚙\~O_O~/⚙♲♙ | 2021-07-26 12:00:04 | 巴幣 4 | 人氣 261

題目: 312. Burst Balloons
難度: Hard
目前下列解法的時間複雜度: O(n*n)


題目說明

給你一排氣球,上面有數字( >=0 )。
每次刺破氣球時,會獲得"此氣球上的數字"乘上剩下氣球中"位在此氣球兩側的氣球上的數字"。若某一側沒有氣球,則假設該側有顆氣球上面數字為1。
求最高得分。


解法: dp
思考流程如下:
1. 先想想"你現在要刺破最後一顆氣球,以取得你的最後成績",那麼你需要的資訊有:
A. 該氣球的左側氣球,全部被刺破後,最高得分
B. 該氣球的右側氣球,全部被刺破後,最高得分
C. 刺破該氣球會獲得的分數
2. 發揮dp精神: 算過的不要再算
所以:
1. 建立一張表,記錄區間最高成績
2. 在一個區間中假設某個氣球為該區間最後一顆,找出最大成績


source code

創作回應

相關創作

更多創作