Why is dp[i][timeA][timeB] one dimension too many when splitting jobs between two crews?
answer
- what does the table already know?
- every job goes to exactly one crew
- the prefix total is fixed by i
- one component is a function of the others
- track one load, derive the other
basics
~20 sEach of the first i jobs goes to exactly one crew, so timeB always equals the prefix total minus timeA. The third component is derived, not free information: it multiplies states and work by the whole time range while every cell that violates the identity is unreachable. Track timeA and compute timeB.
solid answer
~50 sA component earns a place in the state only if some transition reads it **and** it cannot be recomputed from the rest of the state plus fixed input. Here the invariant `timeA + timeB = prefixTotal(i)` holds by construction, because every job among the first `i` is assigned somewhere, so `timeB` is a function of `(i, timeA)`. Keeping it costs a factor equal to the time range in both cells and work, and all but a one-dimensional slice of the resulting table is unreachable — you pay for cells no assignment can ever produce. Reduce to `dp[i][timeA]`, recover the other crew's load arithmetically at the end. The general discipline matters more than the example: adding a dimension "to be safe" never makes a wrong model right. It splits identical subproblems into duplicates, buys nothing in correctness, and pushes you toward a memory ceiling — while a *missing* dimension, the real risk, stays missing.
go deeper
Be ready to notice when two quantities in a state must always add up to something already known. That relationship means one of them can be computed rather than stored.
Explain the two clauses a component must pass — read by some transition, and not recomputable from the rest — and apply them to each axis of a proposed table before writing the loops.
Demonstrate that you shrink a state by finding an invariant, not by guessing, and that you can say what the surplus axis cost in cells and work. Be ready to show which cells were unreachable and why.
Own the standard: every dimension carries a written meaning and a justification, so growth in a table is a decision rather than an accident. Push back on adding state to make a test pass, since that habit hides modelling errors under memory the fleet then has to fund.
## The rule: a dimension must be needed and non-derivable State design has one economy rule with two clauses. A component belongs in the state if and only if: 1. **Some transition reads it** — it changes what is legal or what is optimal going forward; and 2. **It cannot be recomputed** from the other components plus the fixed input. Fail the first clause and it is decoration. Fail the second and it is a duplicate of information you already have, stored again under a different name. ## The worked case A day's jobs, `n` of them with durations `d[1..n]`, are split between two crews; both crews start at the beginning of the day, every job goes to exactly one crew, and you want to minimise the time the later crew finishes. The tempting state is `dp[i][timeA][timeB]` — "having assigned the first `i` jobs, crew A has `timeA` minutes of work and crew B has `timeB`". It is easy to write and obviously correct. It is also wasteful, and the reason is a one-line invariant. Let `P(i)` be the total duration of the first `i` jobs. Since each of those jobs went to exactly one crew, > `timeA + timeB = P(i)` for every reachable cell. `P(i)` is fixed by `i` alone. So `timeB = P(i) - timeA` is **derived**: given the other two components, it carries no information. Every cell where `timeB != P(i) - timeA` is unreachable — never written, never read, purely allocated. The reachable part of the three-dimensional table is a two-dimensional surface inside it. Drop the derived component: > `dp[i][t]` = true if some assignment of the first `i` jobs gives crew A exactly `t` minutes. > > `dp[i][t] = dp[i-1][t] or dp[i-1][t - d[i]]` (the second term when `t >= d[i]`). > > Base: `dp[0][0] = true`, everything else false. Answer: over reachable `t`, minimise `max(t, P(n) - t)`. The scale difference is concrete. With 200 jobs and a 480-minute day, `dp[i][t]` is about 96,000 cells — trivial. `dp[i][timeA][timeB]` is about 46 million, of which roughly one part in 481 can ever be reached. That is the difference between a table you never think about and one that forces a conversation about memory before the feature ships. ## "More state can only make it more correct" is false This is the belief the question is really aimed at, and it deserves a direct answer: **a surplus dimension cannot fix a wrong model, and it can hide one.** - It does not add expressiveness. Duplicated cells hold the same answers under different keys. - It costs time and memory proportionally to the added range, on every input. - It degrades the diagnostic value of the table. When you cannot say what a component means, you also cannot check the transitions against it, and a real modelling error — a rule the state fails to distinguish — hides comfortably among the noise. The asymmetry is worth internalising: a **missing** dimension produces wrong answers that look plausible; a **surplus** dimension produces correct answers at inflated cost. Both are defects, but you cannot fix the first by over-supplying the second. The cure for uncertainty is to state each component's meaning in words and test it against the two clauses, not to add components until the tests pass. ## When the same-looking dimension is genuinely needed Derivability is a property of the *rules*, not of the shape of the state, so a small change to the problem can promote a redundant component to a required one: - **Jobs may be dropped or deferred to tomorrow.** Then the assigned total is no longer `P(i)`, the invariant dissolves, and both loads (or the assigned total plus one load) must be tracked. - **A crew must rest after a run of consecutive jobs.** Now "which crew took the last job" and "how long its current run is" are real components: no transition can recompute them from `i` and `timeA`, and the legality of the next assignment depends on them. - **A cap on the number of jobs per crew.** The count is not derivable from durations, so it is a genuine third component — and its range is `n`, not the whole time axis, which is a much cheaper price. Each of those passes both clauses. That is what a justified dimension looks like, and it is the contrast that makes the redundant one obvious. ## Saying it well in an interview Don't lead with "that's too much memory". Lead with the invariant: "every job is assigned, so the two loads sum to the prefix total — the second load is determined by the first, so I'll track one and derive the other." That sentence proves you designed the state rather than guessed it, and it generalises: the same move — spotting a conservation law among components and dropping the dependent one — is how most large DP tables get smaller without any loss of expressiveness.
- Give a change to the problem that would make tracking both crew totals genuinely necessary.Allow jobs to be dropped or deferred. Then the assigned total is no longer the prefix sum, the conservation identity dissolves, and one load stops determining the other. The test never changes: a component stays only when no transition can recompute it from the remaining state plus fixed input.
- How do you decide during design whether a candidate component belongs in the state?Two clauses. First, does any transition actually read it, so that it changes what is legal or optimal ahead? Second, could it be recomputed from the other components plus the input? Keep it only when the answer is yes to the first and no to the second; otherwise it is decoration or a duplicate stored under a new name.
- What is the harm in keeping a derived component for readability?Readability is worth a comment or a helper that computes it, not a dimension. As a dimension it multiplies cells and work by its whole range, fills the table with unreachable entries, and weakens your ability to reason about the model, since a component with no independent meaning cannot be checked against the transitions.
- Someone proposes adding a dimension because a failing test then passes. How do you respond?Ask what the new component means and which transition reads it. A dimension that fixes a test without a stated meaning is usually masking a missing distinction elsewhere — the merged histories that caused the wrong answer are still merged, and the new axis just happens to separate them on that input. Name the rule the state fails to capture, then model it.
Storing both halves of a split bill when the total is known: the second number is not data, it is subtraction you have chosen to store.
saying these in an interview costs you the question
- Says extra dimensions are harmless because they only cost memory
- Adds a dimension whenever a test fails, without giving it a meaning
- Cannot state the invariant linking the two crew totals
- Believes more state always means more correctness
- Argues the redundant table is fine because the answers are right