What does "state" mean in DP?

AlgorithmsJunior~4 min read

Short answer

State in dynamic programming is the minimal and sufficient set of parameters that uniquely describes a subproblem so that its solution can be reused. The number of all possible states determines the memory usage and largely the time needed to solve the problem.

Detailed answer

What state means in DP

State in DP is a formal description of a subproblem through a set of indices/flags/values, by which we:

store the result (for example, minimum, maximum, number of ways, a boolean of possible/not possible);
uniquely distinguish subproblems (no two different subproblems should have the same state);
can express transitions to simpler states (optimal structure).

Typical form: dp[parameters] = the sought value for the subproblem described by these parameters.

How to choose a correct state

Determine exactly what you want to store in dp (minimum/maximum/count/boolean/best profit, and so on).
Identify the parameters that distinguish subproblems: position/index, prefix/suffix length, current capacity/sum, remainder modulo something, flags (taken/not taken), a mask of visited items, the last chosen entity, and so on.
Check the optimal structure: the dp value must be expressible through values in "smaller" states.
Estimate the dimensionality: the number of states must be acceptable in memory and time.
Formulate the transitions and the computation order (top-down with memoization, or bottom-up/tabulation).
Set the base cases (boundaries, empty sets, zero lengths).

How state differs from transitions and the answer

State: the "coordinates" of the subproblem (which subproblem it is).
Transitions: how to get a state from others (the recurrence formula).
Answer: the specific state that corresponds to the original problem (for example, dp[n], dp[n][m], dp[mask_all][last]).

Examples of states and code

1) Fibonacci: dp[n] - the n-th number

State: n. We store: the value F(n). Transition: F(n)=F(n-1)+F(n-2). Base: F(0)=0, F(1)=1.

// Top-down (memoization)
const fibMemo = (function () {
  const memo = new Map();
  memo.set(0, 0);
  memo.set(1, 1);
  function f(n) {
    if (memo.has(n)) return memo.get(n);
    const val = f(n - 1) + f(n - 2);
    memo.set(n, val);
    return val;
  }
  return f;
})();

// Bottom-up (tabulation)
function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1; // dp[n-2], dp[n-1]
  for (let i = 2; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

2) Number of paths in a grid with obstacles: dp[i][j]

State: cell (i, j). We store: the number of paths to (i, j). Transition: dp[i][j]=dp[i-1][j]+dp[i][j-1], if there's no obstacle. Base: dp[0][0]=1, if the start has no obstacle.

function uniquePathsWithObstacles(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(0));
  if (grid[0][0] === 1) return 0;
  dp[0][0] = 1;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) { dp[i][j] = 0; continue; }
      if (i === 0 && j === 0) continue;
      const fromTop = i > 0 ? dp[i - 1][j] : 0;
      const fromLeft = j > 0 ? dp[i][j - 1] : 0;
      dp[i][j] = fromTop + fromLeft;
    }
  }
  return dp[m - 1][n - 1];
}

3) 0/1 Knapsack: dp[i][w]

State: (i, w), considering the first i items at available capacity w. We store: the maximum value. Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) when w >= weight[i]. Base: dp[0][*]=0.

function knapSack(capacity, weights, values) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]; // don't take item i
      if (w >= weights[i - 1]) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }
  return dp[n][capacity];
}

// Memory optimization (rolling array)
function knapSack1D(capacity, weights, values) {
  const n = weights.length;
  const dp = Array(capacity + 1).fill(0);
  for (let i = 0; i < n; i++) {
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

4) DP over subsets (a TSP example): dp[mask][i]

State: (mask, i), we have visited the set of vertices mask and are currently at i. We store: the minimum path cost. Transition: dp[mask][i] = min_j dp[mask \ {i}][j] + cost[j][i]. Base: dp[1<<start][start] = 0. Here, compressing the state through a bitmask is important.

function tsp(cost) {
  const n = cost.length;
  const N = 1 << n;
  const INF = 1e15;
  const start = 0;
  const dp = Array.from({ length: N }, () => Array(n).fill(INF));
  dp[1 << start][start] = 0;
  for (let mask = 0; mask < N; mask++) {
    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) === 0) continue;
      const cur = dp[mask][i];
      if (cur >= INF) continue;
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;
        const nextMask = mask | (1 << j);
        dp[nextMask][j] = Math.min(dp[nextMask][j], cur + cost[i][j]);
      }
    }
  }
  let ans = INF;
  for (let i = 0; i < n; i++) {
    ans = Math.min(ans, dp[N - 1][i] + cost[i][start]);
  }
  return ans;
}

Estimating complexity through the state

Time ≈ (number of states) x (average number of transitions per state). Memory ≈ number of states (accounting for optimizations, for example rolling arrays or bitmask compression).

Fibonacci: O(n) states, O(1) transitions -> O(n) time, O(1)/O(n) memory.
Knapsack: O(nW) states, O(1) transitions -> O(nW) time, O(n*W) or O(W) memory.
TSP with bitmasks: O(n2^n) states, O(n) transitions -> O(n^22^n) time, O(n*2^n) memory.

Common mistakes when defining the state

Insufficient state: a parameter the answer depends on was left out (leads to incorrect reuse).
Excessive state: an extra parameter was added -> a blowup in dimensionality and resources.
Wrong traversal order in bottom-up: using states that are not yet computed.
Poor initialization: forgotten base cases, incorrect default values (for example, -Infinity/Infinity instead of 0).
Duplicated subproblems: incorrect state encoding (for example, unordered pairs without normalization).

Short checklist for state in DP

What am I storing in dp? (minimum/maximum/count/boolean/best)
Which parameters uniquely describe the subproblem? (indices, flags, masks...)
Is there optimal structure and correct transitions?
Is the dimensionality acceptable in time/memory? (is compression possible)
Have the correct initialization and computation order been chosen?

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.