dp(i, j, k)

  • The maximum score obtainable from the subarray boxes[i…j], given the context that k identical boxes follow boxes[j]. It includes the points obtained by optimally handling the boxes[i…j] segment in the context of the k following boxes, which often involves removing those k boxes as part of a larger group connected to boxes[j].
  • The calculation finds the best score from this entire situation, which might involve grouping boxes[j] with those k followers. The state isn’t just about the score within [i, j], but the total score achievable from the setup described by i, j, and k.
  • Base case: dp(i,j, k) = 0 when i > j
  • Options
    • Merge the rightmost continous block first
    • Merge an intermediate block first, so that the rightmost continous block can be longer

Why is this problem confusing

While maybe not the most common introductory pattern, augmenting DP states with information about external context or future potential appears in more complex problems, such as:

  • Some advanced string DP problems.
  • Optimization problems where decisions within a subproblem are constrained by resources used globally or in adjacent subproblems.
  • Problems involving intervals where actions within the interval affect its boundaries or what can happen outside.

Why top down and not bottom up

  • Handling Complex Dependencies: The state dp[i][j][k] depends on states involving smaller ranges (j’ < j) but potentially larger values of k (e.g., dp[i][m][k+1] depends on dp[i][m][k’] where k’ > k). Figuring out the precise order to fill the 3D dp table iteratively in a bottom-up fashion can be quite tricky. You’d need a carefully constructed set of nested loops (likely iterating by subarray length len = j-i+1, then i, then perhaps k?) ensuring that whenever dp[i][j][k] is computed, all states it depends upon are already available. This can be complex and error-prone.
  • Potentially Sparse State Space: While the theoretical maximum number of states is O(N^3), not all combinations of (i, j, k) might actually be reachable starting from the initial call solve(0, n-1, 0). Top-down only explores and computes the states that are actually relevant to the final answer. A bottom-up approach typically iterates through and fills potentially all O(N^3) states defined by its loops, which might include unnecessary calculations (though using a dictionary for memoization in top-down helps mainly with implementation ease rather than asymptotic complexity here, as most states are likely reachable).

Gotchas

  • Base case should be 0
  • When finding the continous block, it needs to be within the range of the [i, j]