Leetcode 練習:2022-01-01

January 01, 2022

Burst Balloons

題號:312

首先,在 nums 的最前面和最後面都加上 1,並令其長度為 ll(原先的 nums 的長度只有 l2l - 2)。

nums = [1, ...nums, 1]
const l = nums.length

為了方便討論,我們可以令對應到 nums 的矩陣 nj\lang n_j \rang 為:

nj=[n0(=1)n1...nl2nl1(=1)].\lang n_{j} \rang = \begin{bmatrix} n_0(= 1) &n_1 &... &n_{l-2} &n_{l-1} (= 1) \end{bmatrix}.

並且以 njin^i_j 來表示數列 ni,ni+1,...,nj\lang n_i,n_{i+1}, ... ,n_{j} \rangiji\leq j


接著,令 dp 對應到一個 l×ll \times l 矩陣 DD(事實上,這個 dp 在程式的意義上就是矩陣)。要初始化這個矩陣,並且令所有的 Dij=0D_{ij} = 0(方便後續計算),只需要:

const dp = [...Array(l)].map(() => Array(l).fill(0))

即:

// 偽代碼
const dp = [
  [0,0, ..., 0],
  [0,0, ..., 0],
  ...
  [0,0, ..., 0]
]

就結果來說我們希望 dp[i][j]DijD_{ij})記錄了在考慮 njin^i_j 這個數列時,也就是考慮準備要先爆破第 ii 個到第 jj 個間的氣球時,明智地爆破這些氣球所能獲得的最多金幣。

如果這樣,D1,l2D_{1,l-2} 即為所求。

我們期待 DD 是一個上半矩陣,並且在邊緣的地方都為 0(注意:我們不會計算出所有的量,這個矩陣可以當成我們的理論目標,但不會是我們最終計算出來的 dp):

D=[D0,0(=0)D0,1(=0)...D0,l1(=0)0D1,1(=n0n1n2)...D1,l1(=0)00...D2,l1(=0)............00...Dl1,l1(=0)].D = \begin{bmatrix}D_{0,0}(=0) &D_{0,1}(=0) &... &D_{0,l-1}(=0) \\0 &D_{1,1}(=n_0n_1n_2) &... &D_{1,l-1}(=0) \\0 &0 &... &D_{2,l-1}(=0) \\... &... &... &... \\0 &0 &... &D_{l-1,l-1}(=0)\end{bmatrix}.


接下來就是要計算 DijD_{ij}

因為 DijD_{ij} 是唯一的,我們可以假設一個函數 M:{0,...,l1}×{0,...,l1}NM: \{ 0, ...,l-1 \} \times \{ 0, ...,l-1 \} \rightarrow \N 使得

M(i,j)=DijM(i,j) = D_{ij}

考慮任意的 i<k<ji<k<j。對於所有介於 iijj 之間的 kk,當做是我們最後才要來爆破 kknkn_k 會把 njin^i_j 分成兩段:

ni,ni+1,...,nk1,nk,nk+1,...,nj1,nj\lang \textcolor{green}{n_i, n_{i+1}, ..., n_{k-1}}, n_k, \textcolor{red}{n_{k+1}, ..., n_{j-1}, n_{j}} \rang

前半部的爆破所獲錢幣最大值是 M(i,k1)M(i,k-1),後半部的最大值是 M(k+1,j)M(k+1,j),最後加上爆破 kk 所獲得的錢幣,因為這兩段都爆破了,還未爆破的左邊現在是 ni1n_{i-1},右邊則是 nj+1n_{j+1}

但在邊緣的案例上,譬如,k=i<jk=i<j 的時候,上面的圖示就不管用了。但在邊緣的案例上,我們其實只需要考慮爆破其中一邊就好,也就是我們可以希望 M(i,i1)=0M(i, i-1) = 0,但因為 DD 是一個上半矩陣(這就是我們為何一開始要把 dp 填滿 0)這件事情會是對的。同理,i<k=ji<k=ji=k=ji=k=j 的狀況也是如此。

寫成式子即為:

M(i,j)=maxikj({M(i,k1)+M(k+1,j)+ni1×nk×nj+1})M(i,j) = \max_{i\leq k \leq j}(\{ M(i,k-1) + M(k+1,j) + n_{i-1} \times n_k \times n_{j+1} \})

程式碼為:

for (var k = i; k <= j; k++) {
  dp[i][j] = Math.max(
    dp[i][j],
    dp[i][k-1] + dp[k+1][j] +
      nums[i-1] * nums[k] * nums[j+1]
  )
}

接下來就是考慮迭代範圍:

  1. 對每個小於 l - 1 (記得 nums 實際上的長度只有 l - 2)的長度 len 以及 i 做迭代。
  2. 當給定 leni,我們會有唯一的 j,使得 j = i + len - 1
for (var len = 1; len < l - 1; len++) {
  for (var i = 1; i + len - 1 < l - 1; i++) {
    ......
  }
}

我們最後的程式碼因此是:

var maxCoins = function(nums) {
  nums = [1, ...nums, 1]
  const l = nums.length
  
  const dp = [...Array(l)].map(() => Array(l).fill(0))
   
  for (var len = 1; len < l - 1; len++) {
    for (var i = 1; i + len - 1 < l - 1; i++) {
      const j = i + len - 1
      for (var k = i; k <= j; k++) {
        dp[i][j] = Math.max(
          dp[i][j],
          dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]
        )
      }
    }
  }
  
  return dp[1][l-2]
}

Profile picture

Written by Wei Hung who is thinking. You should follow them on Twitter