This is one of the most fundamental ‘aha!’ moments in dynamic programming. Let’s walk through the memory mechanics so you never forget it.

1. The 2D State Transition

In the classic 0/1 Knapsack, the formula is:

dp[i][w] = max(
    dp[i-1][w],                         // Option A: Skip item i (take answer from previous row)
    dp[i-1][w - weight[i]] + value[i]   // Option B: Take item i (add its value to PREVIOUS row at smaller weight)
)

Notice the critical detail: in Option B, dp[i-1][w - weight[i]] comes from row i-1 (before item i was even considered). That is what guarantees you only take item i at most once.

2. Compressing to a 1D Array

Notice that to compute row i, you only ever look at row i-1. You don’t need rows i-2, i-3, etc. So we can just reuse a single 1D array: dp[w].

What happens if you iterate FORWARD (w = weight[i] to W)?

Suppose item 1 has weight = 2, value = 10 and capacity is 6.

• At w = 2: dp[2] = dp[0] + 10 = 10.
• At w = 4: dp[4] = dp[4 - 2] + 10 = dp[2] + 10 = 10 + 10 = 20! (Wait, you just reused item 1 twice!)
• At w = 6: dp[6] = dp[4] + 10 = 30! (You used item 1 three times!)

Because you updated smaller weights first, larger weights read the already updated values from the current item. That turns it into Unbounded Knapsack (infinite items)!

What happens if you iterate BACKWARD (w = W down to weight[i])?

• At w = 6: reads dp[4] (which is still 0 from the previous item!). dp[6] = 0 + 10 = 10.
• At w = 4: reads dp[2] (which is still 0!). dp[4] = 0 + 10 = 10.
• At w = 2: reads dp[0] (which is 0!). dp[2] = 0 + 10 = 10.

By sweeping backwards, whenever you query w - weight[i], that smaller index has not yet been touched for the current item. It still holds the pristine value from item i-1!

Production Python 3.12 Implementation

def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    """Solves 0/1 Knapsack with O(W) auxiliary memory."""
    dp = [0] * (capacity + 1)

    for w_i, v_i in zip(weights, values):
        # Sweep backwards from capacity down to the item's weight
        for w in range(capacity, w_i - 1, -1):
            dp[w] = max(dp[w], dp[w - w_i] + v_i)

    return dp[capacity]

Summary Rule of Thumb

• 0/1 Knapsack (items used at most once) → Iterate Backward (W → weight).
• Unbounded Knapsack / Coin Change (items can be reused infinitely) → Iterate Forward (weight → W).

Building an LRU cache from scratch is one of the best ways to understand how data structures combine in real systems. The industry standard pattern is combining two complementary structures:

1. A Hash Map: Gives you O(1) key-to-node lookups.
2. A Doubly Linked List (DLL) with Dummy Head & Tail: Gives you O(1) node insertion at the front (most recent) and O(1) node removal from the back (least recent).

The secret trick that eliminates 90% of bug-prone null checks is using sentinel (dummy) head and tail nodes. Instead of constantly checking if (head == null) or if (node->prev == null), the dummy head and tail are always linked together: head <-> tail. Any real data node always lives safely in between them!

Architectural Diagram

[Head Dummy] <---> [Most Recent Node] <---> [Older Node] <---> [Tail Dummy]
                                                                      ^
                                                      Evict from here |

Clean, Idiomatic Python 3.12 Implementation

class Node:
    __slots__ = ('key', 'val', 'prev', 'next')
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache: dict[int, Node] = {}
        
        # Dummy sentinel boundaries
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        """Unlinks a node from its current position."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_at_front(self, node: Node) -> None:
        """Inserts node right after head (most recently used)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # Refresh access: move to front
        self._remove(node)
        self._insert_at_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._insert_at_front(node)
        else:
            if len(self.cache) >= self.cap:
                # Evict least recently used (node right before tail)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
                
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._insert_at_front(new_node)

Why Storing the Key Inside the Node is Crucial

Notice that the Node class stores both key and val. Many developers forget to store key in the node and only store val. But when the cache reaches full capacity and you evict tail.prev, how do you delete that entry from the hash map? Without node.key, you’d have to search the entire hash map in O(N) time, destroying your O(1) guarantee!

Thread Safety in Production

If multiple threads access this cache concurrently:

• In Python, use threading.Lock() around get and put.
• In Go or C++, a Read-Write Lock (sync.RWMutex / std::shared_mutex) is often tempting, but remember: even a get() operation mutates the linked list (to move the accessed item to the front)! Therefore, standard read locks are not enough—you must acquire an exclusive lock or use lock striping across multiple shards.