Optimization Techniques

From Correct To Lean

In Bottom-Up Dynamic Programming, you practiced building tables in dependency order. That gives us correctness and predictable runtime.

Now we ask the senior-engineer question: what can we safely remove?

Optimization techniques in DP usually target three things:

• Space: Do we really need the entire table?
• State: Are we tracking variables that do not affect the future?
• Transitions: Are we recomputing a range, max, min, or sum again and again?

This is similar to tuning a service: first make it correct, then inspect memory, hot loops, and unnecessary work. In DP, the same mindset turns a passable solution into an interview-ready one.

Optimize The State

A DP state should contain only the information needed to decide the future.

If two states have the same future behavior, they can often be merged.

Ask:

1. What choices remain from here?
2. What previous facts affect those choices?
3. Can any variable be derived instead of stored?

For example, in a step-cost problem from earlier lessons, dp[i] means: minimum cost to reach step i. We do not need to store the full path for every i if the question only asks for the minimum cost.

That distinction matters:

• Need only the optimal value? Store less.
• Need to reconstruct the exact path? You may need parent pointers or extra metadata.

Optimization is not about deleting data randomly. It is about preserving the recurrence while removing state that does not change the answer.

Rolling Arrays

A common bottom-up optimization is replacing a full DP array with a few variables.

Use this when each state only depends on a fixed number of earlier states.

For the step-cost recurrence:

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

dp[i] only needs the previous two values. So instead of storing dp[0...n], we keep:

• twoBack for dp[i - 2]
• oneBack for dp[i - 1]
• current for dp[i]

This changes space from O(n) to O(1) while keeping runtime O(n).

```javascript
function minCostClimbingStairs(cost) {
  // dp[0] = 0, dp[1] = 0
  let twoBack = 0;
  let oneBack = 0;

  for (let i = 2; i <= cost.length; i++) {
    const takeOneStep = oneBack + cost[i - 1];
    const takeTwoSteps = twoBack + cost[i - 2];
    const current = Math.min(takeOneStep, takeTwoSteps);

    twoBack = oneBack;
    oneBack = current;
  }

  return oneBack;
}

console.log(minCostClimbingStairs([10, 15, 20])); // 15
console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])); // 6
```

Space Compression Check

Suppose a bottom-up DP table has rows i and columns j.

Each cell dp[i][j] depends only on values from dp[i - 1][...], never from older rows like dp[i - 2].

What is the most likely safe space optimization?

Loop Order Matters

When compressing space, the recurrence does not change — but the update order becomes part of correctness.

With a full table, old and new states are naturally separated:

previous row -> current row

With one array, old and new values share the same memory:

same array before update -> same array after update

That means a loop can accidentally read a value that was just updated in the same iteration.

A practical rule:

• If the current item/state should be used at most once, iterate backward over the compressed dimension.
• If it may be reused multiple times, forward iteration may be appropriate.

This is one of the most common places where an otherwise correct DP gets subtly broken.

Knapsack In Place

Here is the classic in-place update trap.

In 0/1 knapsack, each item can be chosen at most once. If we update capacity from low to high, the same item can be reused immediately because the array already contains the new value.

Backward iteration prevents that by making each item read only values from the previous logical row.

```javascript
function knapsack01(items, capacity, direction) {
  const dp = Array(capacity + 1).fill(0);

  for (const item of items) {
    if (direction === "backward") {
      for (let c = capacity; c >= item.weight; c--) {
        dp[c] = Math.max(dp[c], dp[c - item.weight] + item.value);
      }
    } else {
      for (let c = item.weight; c <= capacity; c++) {
        dp[c] = Math.max(dp[c], dp[c - item.weight] + item.value);
      }
    }
  }

  return dp[capacity];
}

const items = [{ weight: 3, value: 4 }];
const capacity = 6;

console.log("Backward 0/1 update:", knapsack01(items, capacity, "backward")); // 4
console.log("Forward accidental reuse:", knapsack01(items, capacity, "forward")); // 8
```

Update Direction

True or false?

In a one-dimensional 0/1 knapsack DP, iterating capacity from low to high is always safe because each item is still processed only once in the outer loop.

Compress Transitions

Sometimes the table size is fine, but each cell is expensive.

Look for transitions like:

dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[i - k]

The naive version recomputes a window of k values for every i, giving O(n * k) time.

But adjacent windows overlap heavily. So we can maintain a running sum:

window = dp[i - 1] + ... + dp[i - k]
dp[i] = window

Then slide the window forward by adding the newest value and removing the value that fell out.

This is the same instinct you would use when optimizing backend metrics over rolling time windows: avoid rescanning the same range when only one element changed.

```javascript
function countWaysToReach(n, maxJump) {
  const dp = Array(n + 1).fill(0);
  dp[0] = 1;

  let windowSum = dp[0];

  for (let i = 1; i <= n; i++) {
    dp[i] = windowSum;

    windowSum += dp[i];

    const indexLeavingWindow = i - maxJump;
    if (indexLeavingWindow >= 0) {
      windowSum -= dp[indexLeavingWindow];
    }
  }

  return dp[n];
}

console.log(countWaysToReach(5, 2)); // 8
console.log(countWaysToReach(5, 3)); // 13
```

Constant Space Blank

A Fibonacci-style DP that keeps only prev2, prev1, and current instead of the entire dp array uses ____ extra space.

Write the asymptotic notation.

Optimization Checklist

When you already have a correct top-down or bottom-up DP, optimize in this order:

1. Preserve the recurrence. Do not optimize before you know what each state means.
2. Inspect dependencies. Does dp[i] need all previous values or only a few?
3. Compress space carefully. Rolling variables, two rows, or one row are common options.
4. Validate update order. Shared memory can cause accidental reuse.
5. Look for repeated transitions. Prefix sums, sliding windows, and cached range values can remove inner loops.
6. Keep reconstruction in mind. If the problem asks for the actual choices, value-only compression may not be enough.

The goal is not cleverness for its own sake. The goal is a solution that is still readable, still correct, and now more efficient.

Next, we will briefly connect this DP toolkit to practical scenarios where these tradeoffs show up outside toy examples.