日1ビッグリート 難易度：ハードデイ

numsという配列の中に、0からn-1までの番号が付けられたn個の風船があります。

すべての風船を突いてください。iの風船を割ると、nums[left] x nums[i] x nums[right]のコインがもらえます。ここで、leftとrightはiの隣にある2つの風船の数字を表しています。風船 i を突くと、風船 left と風船 right が隣り合う風船になることに注意してください。

獲得できるコインの最大枚数を求めます。

内容:

• nums[-1] = nums[n] = 1と仮定することもできますが、これらは実在しないので、つついたり突っついたりすることはできないことに注意してください。
• ≤ n ≤ 500, 0 ≤ nums[i] ≤ 001

例題:

 : [3,1,5,8]
 : 167
 : nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
 coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167

問題:

推論

• すべての可能性を列挙して最大値を求めます。
• まず、スタート地点が定かでなく、スタート地点の後の道も定かではありません。
• スタートは列挙できますが、パスはそうではありません。
• 次に、再帰を使用して、処理された配列を渡すたびに、すべての開始点を再度列挙してみてください。

気付く

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
 let _result = 0
 function maxItem(list, result) {
 if (list.length === 0) {
 _result = Math.max(_result, result)
 return
 }
 for (let i = 0; i < list.length; i++) {
 let item = (list[i - 1] || 1) * list[i] * (list[i + 1] || 1)
 maxItem(
 list.filter((val, index) => index !== i),
 result + item
 )
 }
 }
 maxItem(nums, _result)
 return _result
}

各起点に対して可能なすべての組み合わせが計算され、タイムアウトが予想されました。最適化を考え、すでに発生した組み合わせを保存できないかを優先したところ、i変換の左右の要素は保存する次元がないようで、同様に変化していることがわかりました。

暗記検索

それなら、ポイントを貯めるのではなく、レンジを貯めて試してみるのです：

• 始点iと終点jがあるとします。
• dp[i][j]はiとjの間の風船を破裂させることによって得られる最大の積分を表します。
• dpの範囲：0とnの両方が関係する場合はdp(n+2)。

dp[i][j]の値を取得するには？

• If nums is long 3, it is very simple: dp[0][2] = 0 + nums[0]*nums[1]*nums[2]* + 0 where the first 0 can also be represented by dp[0][1], and the second 0 by dp[0][3] i.e.: dp[0][2] = dp[0][1] + nums[0]*nums[1]*nums[2]* + dp[0][2] = dp[0][2]* + dp[0][3] + nums[0][1]*nums[1]*nums[1]* dp[0][2] = dp[0][2] = dp[0][1] + nums[0][1]*nums[1]*nums[2]* + dp[0][3］
• iからjのdp[i][j]に1つ以上の要素がある場合、結果が複数になるため、すべての結果を最大まで列挙する必要があります iからjの範囲を列挙するポインタをkに設定し、次のようにします。

気付く

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
 // クロージングのデフォルトは1、dpを生成するために加算した後に長さを取る
 nums.unshift(1)
 nums.push(1)
 let len = nums.length,
 dp = Array.from({ length: len }, () => new Array(len).fill(-1))
 // 追加された2つの1を取り除くと、iとjの範囲、すなわち必要な値が得られる。
 return solve(0, len - 1)
 function solve(i, j) {
 // 範囲外 0を返す
 if (i >= j - 1) return 0
 // 範囲はすでに計算されている
 if (dp[i][j] != -1) return dp[i][j]
 for (let k = i + 1; k < j; k++) {
 let sum = nums[i] * nums[k] * nums[j]
 sum += solve(i, k) + solve(k, j)
 dp[i][j] = Math.max(dp[i][j], sum)
 }
 return dp[i][j]
 }
 return dp[0][len - 1]
}

動的プログラミング

• iとjの境界からの列挙
• また [i][j]依存関係 dp[i][k]、dp[k][j]
• つまり、dp[i][j]の計算では、dp[i][k]、dp[k][j]を知る必要があり、例で見ると、iは0、jは5で、dp[1][3]の要求を設定し、kは2でdp[1][2]、dp[2][3]を知る必要があります。

iは最大から最小まで変化させる必要があることがわかります。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function (nums) {
 nums.unshift(1)
 nums.push(1)
 let len = nums.length,
 dp = Array.from({ length: len }, () => new Array(len).fill(0))
 // デフォルトのパディング1ではパンクできないので、iはlen-2-1で囲まれる。
 for (let i = len - 3; i >= 0; i--) {
 // i<j,であれば、jはiに最小化され、デフォルトはuniである。+1
 for (let j = i + 2; j < len; j++) {
 for (let k = i + 1; k < j; k++) {
 dp[i][j] = Math.max(
 dp[i][j],
 dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
 )
 }
 }
 }
 return dp[0][len - 1]
}

ブログ：

出版：The Pit's Little Bookie