Patterns

dp[i][j] over interval (i,j); inner loop over split point k

When to useBurst balloons, matrix chain multiplication, palindrome partitioning

DECLARE

dp = n × n table; pad input with sentinels if helpful

—

const dp = Array.from({length: n}, () => new Array(n).fill(false));

const padded = [1, ...targets, 1];
const n = padded.length;
const dp = Array.from({length: n}, () => new Array(n).fill(0));

—

BASE CASES

length-1 intervals = 0 (or trivial value)

—

for (let i = 0; i < n; i++) { dp[i][i] = true; count++; }

// implicit: dp initialized to 0; adjacent-sentinel pairs have no targets to burst

—

BUILD

outer: for length 1..n; inner: for i (j = i + length - 1); innermost: for k = i..j

—

for (let length = 2; length <= n; length++) {

for (let len = 2; len < n; len++) {

—

[RECURRENCE]

dp[i][j] = max/min over splits at k

    dp[i][j] = Math.max(
      coins[i] - dp[i + 1][j],
      coins[j] - dp[i][j - 1]
    );

    dp[l][r] = s[l] === s[r] && (length === 2 || dp[l+1][r-1]);
    if (dp[l][r]) count++;

      const score = padded[left] * padded[k] * padded[right] + dp[left][k] + dp[k][right];
      dp[left][right] = Math.max(dp[left][right], score);

—

RETURN

return dp[0][n-1]

const total = coins.reduce((s, c) => s + c, 0);
return (total + dp[0][n - 1]) / 2;

return count;

return dp[0][n - 1];

—