DEV Community: Nishant Gaurav

INSERT, SELECT, UPDATE, DELETE: PostgreSQL

Nishant Gaurav — Wed, 14 Oct 2026 17:30:00 +0000

At some point you stop thinking about SQL as "a language" and it just becomes muscle memory — you know what an UPDATE without a WHERE clause does before you even finish typing it, because you've either done it once by accident or heard someone else's horror story about it. That's basically what this article is about. Not anything exotic, just the four commands that make up most of what you actually do day to day, and the handful of ways each one bites people early on.

Why this is worth slowing down for

It's tempting to skim past CRUD because it feels like the "easy" part of SQL — everyone's written a SELECT before. But most of the actual production incidents I've read about, and a couple I've caused myself in test databases on purpose just to see what happens, come from these four commands specifically. Not from window functions or CTEs. From a missing WHERE clause, or a SELECT * that broke when someone renamed a column six months later.

The syntax is simple. The discipline around using it correctly is the part that takes longer to build.

INSERT: getting data in

INSERT INTO venues (name, latitude, longitude)
VALUES ('Van Vihar', 23.2237, 77.3910);

-- multiple rows in one call — fewer round trips, faster
INSERT INTO venues (name, latitude, longitude) VALUES
    ('Upper Lake', 23.2415, 77.3550),
    ('DB Mall', 23.2280, 77.4340);

The multi-row version is worth using whenever you're inserting more than one row at a time, even for something small. It's not just a style preference — one round trip to the database instead of several actually adds up, especially if you're populating a table with anything more than a handful of rows.

Here's a detail that connects back to how Postgres works internally: every INSERT creates a brand new row version. Postgres doesn't have a concept of "editing in place" the way you might picture it. That's tied directly to MVCC, which is a much bigger topic I'll get into properly later in this series — for now it's enough to know that even INSERT isn't as simple under the hood as "write these bytes to a table."

SELECT: the one you'll use more than everything else combined

SELECT name, latitude, longitude
FROM venues
WHERE is_closed = FALSE
ORDER BY name ASC
LIMIT 10 OFFSET 0;

WHERE filters rows before anything gets grouped or aggregated. ORDER BY sorts whatever's left. LIMIT/OFFSET handle pagination, though OFFSET gets slow once a table grows large — that's a topic for the indexing article later on, but it's worth knowing it exists as a limitation now.

The thing that trips people up early, and that I did plenty myself when I was starting out, is reaching for SELECT * out of habit. It's fine while you're exploring data in psql. It's a problem in application code, for a few reasons that aren't obvious until they bite you: it breaks silently if someone adds or renames a column later, it pulls back data you don't actually need, and it can block certain optimizations — like an index-only scan, where Postgres could answer a query using just the index without touching the table at all, but only if it knows exactly which columns you need.

UPDATE: changing what's already there

UPDATE venues
SET is_closed = TRUE
WHERE id = 5;

The one rule here that actually matters: never run an UPDATE without a WHERE clause unless you genuinely mean to update every row in the table. This is one of those things that sounds obvious written down, and then someone runs a query against production instead of the staging environment they meant to be in, and every row silently gets the same value. It happens more than you'd think, usually from copy-pasting a query and forgetting to re-add the WHERE at the end.

DELETE: same warning, different verb

DELETE FROM venues WHERE is_closed = TRUE;

Same logic as UPDATE — no WHERE means "delete everything," and Postgres will do exactly that without complaining, because as far as it's concerned that's a perfectly valid instruction. If you're ever testing a DELETE on something you're not 100% sure about, wrapping it in a transaction first (BEGIN, run the delete, check the result, then COMMIT or ROLLBACK) is a cheap habit that saves you from this exact situation.

Where it actually gets interesting: UPSERT

INSERT INTO venues (id, name, latitude, longitude)
VALUES (5, 'Van Vihar National Park', 23.2237, 77.3910)
ON CONFLICT (id)
DO UPDATE SET name = EXCLUDED.name;

This is Postgres's answer to "insert this row, but if it already exists, update it instead" — a pattern that comes up constantly in real projects. Syncing data from an external API is the most common case: you're pulling venue data from some third-party source on a schedule, and you don't know ahead of time whether a given venue is already in your table or not. Instead of writing a SELECT to check first and then branching into either an INSERT or an UPDATE, ON CONFLICT handles both in one statement.

EXCLUDED refers to the row that would have been inserted if there hadn't been a conflict — so EXCLUDED.name means "the name value from the row I was trying to insert." If you just want to skip duplicates entirely without updating anything, ON CONFLICT DO NOTHING does that.

If you get asked how to handle duplicate key inserts gracefully, this is the expected answer, and it's worth mentioning DO NOTHING alongside DO UPDATE since they solve slightly different problems — one is deduplication, the other is a real upsert.

Putting it together: syncing venue data from an external source

Say your dashboard pulls venue data from a city API once a day, and venues can be added, renamed, or marked closed on their end. Here's roughly how that sync would actually look, combining a few of these commands:

INSERT INTO venues (id, name, latitude, longitude, is_closed)
VALUES (12, 'Central Park Cafe', 23.2510, 77.4020, FALSE)
ON CONFLICT (id)
DO UPDATE SET
    name = EXCLUDED.name,
    is_closed = EXCLUDED.is_closed;

Run once per venue returned from the API, this single statement handles both new venues and updates to existing ones, without you needing to check which case you're in first. Compare that to the naive version — a SELECT to check existence, then an if/else in application code choosing between INSERT and UPDATE — and it's not just shorter, it also avoids a race condition where two sync jobs running close together could both decide the row doesn't exist yet and both try to insert it.

Where this leaves you

These four commands, plus ON CONFLICT, cover most of what you'll actually type against a database in a normal week. The syntax isn't the hard part — the discipline of always including WHERE on anything destructive, and reaching for ON CONFLICT instead of a manual check-then-branch pattern, is what actually separates code that survives contact with real data from code that doesn't.

Next up: constraints — how to make bad data structurally impossible to insert in the first place, instead of relying on catching it after the fact.

PostgreSQL Data Types:

Nishant Gaurav — Tue, 13 Oct 2026 17:30:00 +0000

There's a specific kind of bug that doesn't show up right away. A latitude column stored as FLOAT, and months later your distance calculations are just slightly off in a way that's hard to pin down. Or a price column using the same type, and a customer notices their total is a cent wrong, in a way that somehow compounds across enough transactions to matter. Nobody wrote a bug in the usual sense. The data type was the bug, and it had been sitting there quietly since the table was created.

Choosing a column's type feels like the most mechanical part of designing a schema — pick something that looks roughly right and move on. I used to treat it that way too. It's actually one of the few decisions that's genuinely annoying to undo later, because by the time you notice it's wrong, there's real data sitting in that column.

A table that works fine until it doesn't

Say you're building a venues table for a dashboard that tracks locations and closures. It's tempting to just reach for whatever feels familiar — VARCHAR for text, FLOAT for anything with a decimal, INTEGER for IDs without thinking twice.

That table inserts rows fine. It passes whatever tests you write in the first week. Then a risk score computed from FLOAT values starts drifting in a way that doesn't reproduce consistently, or the ID column runs into its ceiling because nobody considered BIGINT, or a TIMESTAMP column with no timezone awareness makes an event look like it happened in a different hour depending on which server handled it. None of these are exotic problems. They're just what happens when types don't get real thought up front.

Going through the types one at a time

The table itself

CREATE TABLE venues (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    latitude DOUBLE PRECISION NOT NULL,
    longitude DOUBLE PRECISION NOT NULL,
    is_closed BOOLEAN DEFAULT FALSE,
    created_at TIMESTAMP DEFAULT NOW()
);

This is a fairly realistic starting point for a venue-tracking dashboard. Every type choice here is worth understanding on its own, not just copying because it looked right in a tutorial.

INTEGER / BIGINT — good for counts and IDs. The distinction matters once you think about scale: INTEGER tops out around 2.1 billion. If there's any real chance a table could grow past that — a high-volume events table, say — starting with BIGINT costs nothing now and avoids a painful migration later.

SERIAL / BIGSERIAL — the usual auto-incrementing ID setup. It's worth knowing this isn't actually a separate type. It's an INTEGER (or BIGINT) column backed by a sequence that hands out the next value automatically. That distinction matters later if you ever need to work with the sequence directly.

VARCHAR(n) vs TEXT — this one surprised me coming from MySQL. In Postgres these perform almost identically. TEXT is usually the better default unless you actually need to enforce a maximum length — VARCHAR(n) is really just TEXT with a length constraint bolted on, not a different storage format underneath.

NUMERIC(p,s) vs DOUBLE PRECISION — this is the one that actually causes real incidents. NUMERIC stores exact decimal values. DOUBLE PRECISION is a floating-point approximation. Don't use FLOAT/DOUBLE PRECISION for money — the rounding errors aren't a hypothetical, they show up given enough transactions. DOUBLE PRECISION is fine for something like geospatial coordinates, where the imprecision at that scale doesn't really change the result.

BOOLEAN — flags. Not much to say here.

TIMESTAMP vs TIMESTAMPTZ — TIMESTAMPTZ stores the value normalized to UTC and converts it on display based on the client's timezone. TIMESTAMP just stores whatever you gave it, with no timezone awareness at all. For pretty much any real app — anything with users spread across timezones, or a backend and frontend that might not agree on local time — TIMESTAMPTZ is the safer default, even though TIMESTAMP looks simpler at first glance.

JSONB — binary-stored, indexable, faster to query than JSON, which is just stored as raw text. Anything semi-structured, like a payload synced from a third-party API, belongs in JSONB by default.

UUID — useful when IDs need to be generated somewhere other than the database itself, or across multiple systems, without collision risk. Needs either gen_random_uuid() or an extension like pgcrypto or uuid-ossp.

The two questions that always come up

"Difference between VARCHAR and TEXT?" — functionally almost identical in Postgres, unlike MySQL. VARCHAR(n) just adds a length constraint on top of the same underlying storage.

"Difference between JSON and JSONB?" — JSON stores the exact text, preserving whitespace and key order, but it's slower to query and doesn't support much indexing. JSONB stores a parsed binary format, which loses the exact original formatting but is faster and indexable through GIN indexes. Default to JSONB most of the time, and only reach for plain JSON if you specifically need to preserve the text exactly as it came in.

Altering a table isn't always as harmless as it looks

ALTER TABLE venues ADD COLUMN city VARCHAR(50);
ALTER TABLE venues DROP COLUMN city;
ALTER TABLE venues ALTER COLUMN name TYPE TEXT;
ALTER TABLE venues RENAME COLUMN name TO venue_name;

These look simple, and on a small table they are. The problem shows up at scale — altering a table with millions of rows during peak traffic can lock it, blocking reads and writes for however long the operation takes. ADD COLUMN with a default value used to force a full table rewrite in older Postgres versions. That got a lot cheaper starting in Postgres 11 for constant defaults, but it's worth knowing that history exists, since not every production system runs the latest version, and assuming modern behavior on an older cluster is a reasonable way to cause an outage.

DROP vs TRUNCATE vs DELETE

DROP TABLE venues;          -- removes the table and its structure entirely
TRUNCATE TABLE venues;      -- empties all rows, keeps the structure
DELETE FROM venues;         -- removes rows, can be filtered, slower, undoable within a transaction

DELETE works row by row, gets logged, supports WHERE, and is fully transaction-safe — you can roll it back. TRUNCATE is close to instant because it deallocates whole pages instead of scanning rows one at a time. It can't use WHERE, but it's still transactional in Postgres, so it can be rolled back too, as long as you're inside a transaction that hasn't committed. DROP removes the entire table, structure included, not just what's inside it.

Fixing a type before it becomes a real migration

Say the venues table above shipped with risk_score DOUBLE PRECISION, because someone figured "it's just a number between 0 and 1, a float is fine." A few weeks later, a report comparing risk scores across venues starts showing inconsistent sort order for values that should be identical — classic floating-point comparison drift.

Caught early, the fix is a simple alteration:

ALTER TABLE venues ALTER COLUMN risk_score TYPE NUMERIC(3,2);

Caught after the table has millions of rows, this becomes a much more careful operation — possibly needing a maintenance window, or a safer pattern like adding a new column, backfilling it, and swapping it in. The gap between fixing this on day one and fixing it six months later isn't small. It's the difference between a one-line change and a planned migration.

Where this leaves you

Types in Postgres aren't just about what values a column technically accepts — they carry real assumptions about precision, timezone handling, and scale. Those assumptions are cheap to get right when you're creating the table and expensive to fix once there's data in it. Next time you write a CREATE TABLE, it's worth treating each type as a real decision, especially NUMERIC vs DOUBLE PRECISION for anything money-related, and TIMESTAMPTZ vs TIMESTAMP for anything tied to a user.

Next up: actually working with the data — INSERT, SELECT, UPDATE, DELETE, and the upsert pattern for handling "insert or update" cleanly.

Getting Into PostgreSQL: psql, Connections, and the First Commands You Actually Need

Nishant Gaurav — Mon, 12 Oct 2026 17:30:00 +0000

Most tutorials rush past this part. "Install Postgres, connect, start querying" — as if opening the database is the boring bit you skip through to get to the real content. When I was starting, that gap was exactly where I felt lost. You're connected, technically, but you have no idea what's actually in front of you.

This article covers those first few minutes: getting into psql, figuring out what you're connected to, and a handful of commands that eventually become reflexes if you use Postgres regularly.

Why not knowing your way around costs you time

Say you inherit a project. Someone hands you a connection string, you open psql, and you're in. Now what? You don't know what databases exist on the server. You don't know what tables are in the one you're connected to. Someone mentioned a table in a Slack message three months ago and you have no idea what columns it has.

Without a small set of orientation commands, every one of those questions turns into either opening a GUI (if one's set up) or trying to remember how to query Postgres's internal system catalogs directly, which honestly nobody has memorized. There's a small handful of psql shortcuts that answer all of this in a couple of seconds, and once they're second nature, this stops being a problem.

Connecting, and the commands that orient you

Connecting

psql -U username -d database_name -h host -p 5432

Each flag does one job:

-U — the user you're connecting as
-d — the database to connect to
-h — the host, a remote server or localhost
-p — the port, and 5432 is Postgres's default. It's a small detail, but it comes up as a quick sanity-check question fairly often.

A few commands worth knowing by heart

Once you're inside psql, there's a set of meta-commands — not SQL, just shortcuts specific to psql itself, which is why they start with a backslash and don't need a semicolon:

Command	What it does
`\l`	list databases
`\c dbname`	connect to a database
`\dt`	list tables in the current schema
`\d tablename`	describe a table — columns, types, constraints, indexes
`\du`	list roles/users
`\q`	quit

\d tablename is the one I use the most. It's the fastest way to see what a table actually looks like without leaving the terminal, and it shows constraints and indexes too, not just column names — something a plain SELECT * LIMIT 1 won't tell you.

Why these are separate from SQL

psql splits things into two categories on purpose. SQL is for talking to the database engine about your data — it gets parsed, planned, and executed on the server. Meta-commands are for talking to the client about your environment, so \dt doesn't need a semicolon and responds more or less instantly, because it's not going through the same query pipeline.

If you get asked how to check a table's structure without a GUI, \d tablename is basically the expected answer. It's less about the command itself and more a quick check on whether you've actually spent time in a terminal with Postgres, versus only clicking around in a visual tool.

Where the confusion usually starts: databases, clusters, templates

Creating and dropping a database

CREATE DATABASE project_db;
DROP DATABASE project_db;

One convention worth knowing early: one database per logical application is the norm. A geospatial dashboard would get its own database, separate from anything unrelated, even if they're sitting on the same server.

In multi-tenant setups, people sometimes reach for "one database per tenant" because it feels like clean isolation. It usually isn't the right call — hundreds of databases becomes a real management headache. A tenant_id column, or separate schemas per tenant within one database, tends to hold up much better as things grow.

What CREATE DATABASE is actually doing

Here's a detail that surprised me the first time I read about it: CREATE DATABASE doesn't build an empty database from scratch. It clones a template database — template1 by default. That explains a specific category of confusing bugs. If template1 has an unexpected encoding or locale setting, every database you create afterward quietly inherits it, and the symptoms show up much later as garbled text or sorting that doesn't behave the way you'd expect.

Setting up a project database, step by step

Say you're starting the geospatial dashboard from nothing. Here's roughly how that goes in practice:

psql -U postgres -h localhost -p 5432

You're connected to the default postgres database — not your project's yet, just the entry point.

\l

Confirms nothing named venue_dashboard already exists, so you're not about to collide with something.

CREATE DATABASE venue_dashboard;
\c venue_dashboard

Now you're connected to your project's own database, kept separate from anything else on the server.

\dt

Nothing comes back — no tables yet, which is expected on a fresh database. It also confirms you're actually in the right place before running any CREATE TABLE statements.

Connect, list, create, switch, verify. It's a small sequence, but it's one you end up running at the start of most new projects, and doing it deliberately once means you're not fumbling through it later, especially in something like a live technical interview.

Where this leaves you

The few minutes before your first CREATE TABLE matter more than they seem to. Knowing \dt, \d, and \l well enough that you don't have to think about them, and understanding that CREATE DATABASE clones a template rather than starting from nothing, makes navigating Postgres a lot less stressful day to day.

Next time you sit down in psql, even in a database you know well, try running the orientation commands first anyway. It's a small habit, but it holds up well as the number of databases and tables you're dealing with grows.

Next up: actually shaping data — tables, data types, and constraints that make bad data hard to insert in the first place.

Egg Dropping: Min Outside, Max Inside

Nishant Gaurav — Sat, 10 Oct 2026 12:30:00 +0000

Scrambled String needed an extra dimension because a substring couldn't be pinned down by position alone, it also needed a length. Egg Dropping needs something different again: the partition point k isn't a place in a string this time, it's an actual floor of a building, and for the first time in this series, the combining step has to account for the fact that you don't get to see the outcome of your own choice before committing to it.

The Problem

You have E eggs and a building with F floors. There's some unknown threshold floor: eggs dropped from it or below survive, eggs dropped above it break. You want to find that threshold using as few drops as possible, but you have to plan for the worst case, since you don't know in advance which floor the threshold actually is.

Floor:   1  2  3  4  5  6  7  8  9  10
         ok ok ok ok ok break break break break break

Here the threshold is floor 5. The egg survives dropped from there, and breaks from floor 6 onward. If you tested floors one at a time starting from the bottom, you could end up needing all the way up to F drops in the worst case, since the threshold could turn out to be the very last floor you try. The goal is a strategy that guarantees finding the threshold using as few worst-case attempts as possible.

Picking a Floor to Test

Say you drop an egg from floor k. There are exactly two outcomes, and each one tells you something different about where the threshold has to be.

          10
           9
           8
           7
           6
          --------------
           5   <- drop here
          --------------
           4
           3
           2
           1

The egg breaks. The threshold has to be below k. Every floor at k and above is now known to break, so the search space shrinks to floors 1 through k-1. You've also used up one of your eggs, since it just broke, so you're left with E-1 eggs and k-1 floors still to search.

subproblem: solve(E - 1, k - 1)

The egg survives. The threshold has to be at k or above. Floors below k are ruled out, and the search space becomes k+1 through F, a span of F-k floors. Since the egg survived, you still have all E eggs, just fewer floors left to check.

subproblem: solve(E, F - k)

                     Drop at k
                         |
              +----------+----------+
              |                     |
            Break                No Break
              |                     |
        E - 1 eggs                E eggs
        k - 1 floors             F - k floors
              |                     |
       solve(E-1, k-1)         solve(E, F-k)

Here's the part that's genuinely new compared to every problem earlier in this series. You don't get to choose which of these two outcomes happens. The egg either breaks or it doesn't, and you have no control over that, and no way to know in advance. So whatever strategy you commit to has to be judged by its worst possible outcome, not its best one. That means the two branches get combined with max, not the min or the sum seen in earlier chapters:

1 + max(solve(E - 1, k - 1), solve(E, F - k))

The +1 accounts for the drop you just made, which counts as one attempt regardless of which way it goes.

Why This Still Looks Like MCM

The core move is identical to every problem in this series so far: try every possible partition point, solve two subproblems, combine them. What's different is the shape of the combination.

for k in range(1, F + 1):

Every earlier problem in this family picked the best partition using a min over k. Egg Dropping does that too, but with a twist: at each individual k, you first have to brace for the worse of the two outcomes with max, and only after that do you compare across different values of k with min, looking for whichever floor gives the smallest worst-case guarantee.

                   MIN (choose the best floor)
                    |
       +------------+------------+
       k=1         k=2          k=3 ...
        |            |             |
      MAX          MAX           MAX  (brace for the worse outcome)
     /    \        /    \        /    \
 break  survive  break  survive break  survive

That min-outside, max-inside structure is the actual signature of this problem, and it's worth naming explicitly, because it's the piece that's genuinely new. Every earlier problem in this series only ever needed one of the two: MCM and Palindrome Partitioning only needed min, Boolean Parenthesization only needed sums, Scrambled String only needed a boolean or. This is the first one that needs both a min and a max at once, nested inside each other, because you're optimizing a strategy against an adversary you can't predict.

dp(E, F) = min over 1 <= k <= F of { 1 + max(dp(E - 1, k - 1), dp(E, F - k)) }

The Base Cases

Three conditions end the recursion.

No floors left (F == 0): nothing to test, zero attempts needed.

One floor left (F == 1): there's nothing to narrow down, one drop settles it, so it's one attempt either way.

Down to one egg (E == 1): this one is worth sitting with, because it's the case where the whole partitioning strategy stops being available to you. With only one egg left, you can no longer afford the risk of testing high up and having it break, since a single break with no eggs left in reserve means you can't continue testing at all. The only safe strategy left is testing floors one at a time from the bottom, which means the worst case is F attempts, testing every floor in sequence until you find the one that breaks.

if F == 0 or F == 1:
    return F

if E == 1:
    return F

The Recursive Solution

class Solution:

    def solve(self, E, F):

        if F == 0 or F == 1:
            return F

        if E == 1:
            return F

        ans = float('inf')

        for k in range(1, F + 1):

            break_case = self.solve(E - 1, k - 1)
            no_break_case = self.solve(E, F - k)

            attempts = 1 + max(break_case, no_break_case)

            ans = min(ans, attempts)

        return ans

    def eggDrop(self, E, F):
        return self.solve(E, F)

A Small Example: E = 2, F = 3

Try dropping at floor k = 2.

If it breaks: one egg left, one floor left below (floor 1) to check. solve(1, 1) = 1 attempt.

If it survives: two eggs still available, one floor left above (floor 3) to check. solve(2, 1) = 1 attempt.

attempts at k = 2 = 1 + max(1, 1) = 2

With 2 eggs and 3 floors, dropping first at floor 2 guarantees finding the threshold in at most 2 attempts, regardless of which way that first drop goes.

Two Ways to Represent the Same State

Just like Scrambled String had a dictionary version and an index-based version describing the same subproblem, Egg Dropping has an equivalent choice, whether to model floors as an explicit range (i, j) or as a simple count F.

Explicit interval: solve(E, i, j), tracking the actual floor boundaries. A partition at k splits the break case into i through k-1 and the survive case into k+1 through j.

min over i <= k <= j of { 1 + max(solve(E - 1, i, k - 1), solve(E, k + 1, j)) }

Relative span: solve(E, F), tracking only how many untested floors remain, not their absolute labels.

The reason the simpler version works here, and it's a genuinely useful thing to notice, is that this problem doesn't care which specific floors remain, only how many. Floors 4 through 10 behave identically to floors 1 through 7 as far as the strategy is concerned, since nothing about the problem references a floor's absolute position, only the count of floors still left to search. That's different from something like Palindrome Partitioning, where the actual characters at each position mattered, not just how many characters were left. Because Egg Dropping's subproblems only ever depend on a count, the 2D state (E, F) is already complete, with no need for the extra index bookkeeping that Scrambled String's length dimension required.

Memoization: A 2D Table

Since only two things change between subproblems, the number of eggs and the number of remaining floors, an (E+1) x (F+1) table covers the entire state space.

        F ->
E |    0  1  2  3  4  5 ...
      ---------------------
  1  |
  2  |
  3  |
  4  |

class Solution:

    def solve(self, E, F, T):

        if F == 0 or F == 1:
            return F

        if E == 1:
            return F

        if T[E][F] != -1:
            return T[E][F]

        ans = float('inf')

        for k in range(1, F + 1):

            break_case = self.solve(E - 1, k - 1, T)
            no_break_case = self.solve(E, F - k, T)

            attempts = 1 + max(break_case, no_break_case)

            ans = min(ans, attempts)

        T[E][F] = ans

        return T[E][F]

    def eggDrop(self, E, F):

        T = [[-1] * (F + 1) for _ in range(E + 1)]

        return self.solve(E, F, T)

This is the same memoization pattern from every earlier chapter, check before computing, store after, just keyed on (E, F) instead of (i, j).

The Interval DP Family, Side by Side

	Partition point	Subproblems	Combination	Objective	State
MCM	k between matrices	solve(i,k), solve(k+1,j)	left + right + scalar cost	min	2D: T[i][j]
Palindrome Partitioning	k between string indices	solve(i,k), solve(k+1,j)	left + right + 1	min	2D: T[i][j]
Boolean Parenthesization	k at operator positions	left(T/F), right(T/F)	truth table combinations	count (sum)	3D: T[i][j][isTrue]
Scrambled String	k splitting string lengths	no_swap(left,right), swap(left,right)	boolean OR	boolean match	3D: T[i][j][length]
Egg Dropping	k = dropped floor	solve(E-1,k-1), solve(E,F-k)	1 + max(break, survive)	min over k	2D: T[E][F]

Every row in this table shares the same skeleton, boundaries, a loop over k, two subproblems, a combining rule. What's actually been changing chapter to chapter is entirely in the last two or three columns: what the subproblems represent, how they combine, and how many dimensions the state needs to carry. Egg Dropping's real contribution to this table isn't a new kind of partitioning, it's the first appearance of max inside the combination step, sitting underneath the min that every other row in this table already had.

Quick Revision

Egg Dropping
     |
Choose a floor k
     |
     +-----------------------+
     |                       |
   BREAK                  SURVIVE
     |                       |
 E - 1 eggs              E eggs
 k - 1 floors            F - k floors
     |                       |
     +----------+------------+
                |
        max(break, survive)
                |
          + 1 attempt
                |
      try every possible k
                |
             minimum

Base cases:
  F == 0 or F == 1  -> return F
  E == 1            -> return F (must test bottom-up)

Recurrence:
  dp(E, F) = min over k of { 1 + max(dp(E-1, k-1), dp(E, F-k)) }

"min outside, max inside" is the signature of this problem, and more broadly, of interval DP problems where you're minimizing a worst-case guarantee rather than a straightforward cost. The min picks the best strategy available to you. The max accounts for the fact that once you've picked, the outcome isn't yours to control.

What You Now Understand

Egg Dropping keeps the exact partitioning skeleton this whole series has been building on, but it's the first problem where the two subproblems on either side of the split aren't both under your control. One of them happens to you, not because you chose it. That's why max shows up nested inside the min here for the first time: the outer min is you picking the best strategy, and the inner max is bracing for whichever of the two outcomes turns out worse, since you don't get to decide which one you get.

Scrambled String: The MCM Skeleton, Now With Two Strings and a Swap Choice

Nishant Gaurav — Fri, 09 Oct 2026 12:30:00 +0000

Boolean Parenthesization stretched the state from (i, j) to (i, j, isTrue) because a single number stopped being enough to describe a subproblem. Scrambled String stretches things differently. There are now two strings involved instead of one, and at every partition point there's a genuine choice: keep the two halves in order, or swap them. The skeleton is still the same one from MCM. What changes is what counts as a valid match on each side of the split.

The Problem

Given two strings A and B, determine whether B is a scrambled version of A.

A scrambled string comes from repeatedly splitting a string in two and optionally swapping the two halves, recursively, at every level. Picture A = GREAT as a binary tree, where each split produces two children that can optionally be swapped:

             GREAT
            /     \
          GR       EAT
         /  \     /   \
        G    R   E     AT
                       / \
                      A   T

At any non-leaf node in this tree, the two children are allowed to swap places. Swapping GR gives RG. Swapping EAT gives ATE. If enough of these swaps happen at the right places, GREAT can be transformed into some other arrangement, and the question is whether B is reachable from A this way.

A split always has to produce two non-empty parts. Splitting GREAT into GREAT and an empty string isn't a valid partition, so index 0 and index n are both off-limits as split points.

Two things are worth noting before going further. Zero swaps is a completely valid scramble. If A and B are identical, that's a scrambled string with nothing actually scrambled, and it should return True. And if A and B have different lengths, B can never be a scramble of A at all, so that's an immediate False before anything else gets checked.

Recognising the MCM Pattern

The core question, "where can this string be split," is the same question MCM has been asking all along.

GREAT can split at:
  G | REAT
  GR | EAT
  GRE | AT
  GREA | T

String
  |
Can be recursively divided into two parts
  |
Try every possible partition
  |
Check left and right parts
  |
MCM / Interval DP pattern

There's no scalar cost being minimized here the way there was in MCM's multiplication cost or Palindrome Partitioning's cut count. What carries over from MCM isn't the specific thing being optimized, it's the structural template underneath all of these problems: partition, solve the left, solve the right, combine. Scrambled String borrows that template and fills in a completely different combining rule.

What Happens After You Partition

Here's where this problem earns its own identity. Split A at position k, giving A1 = A[0:k] and A2 = A[k:n]. B has to be split to match, but because of the swap rule, there are two different ways B's pieces could correspond to A's pieces.

No swap: A1 should match a same-length piece of B taken from the front, and A2 should match the rest of B.

A1 -> B1 (length k)
A2 -> B2 (length n-k)

Check: solve(A1, B1) and solve(A2, B2)

Swap: A1 should match a same-length piece of B taken from the end, and A2 should match whatever's left at the front of B.

A1 -> B2 (length k)
A2 -> B1 (length n-k)

Check: solve(A1, B2) and solve(A2, B1)

              Split at k
                  |
        ---------------------
        |                   |
    No Swap               Swap
    A1 -> B1               A1 -> B2
    A2 -> B2               A2 -> B1

If either the no-swap combination works or the swap combination works, for any valid k, the whole thing is a match. That's an OR across every partition point, and within each partition point, an AND between the two halves matching. k ranges from 1 to n-1 inclusive, the same non-empty-halves constraint mentioned earlier:

for k in range(1, n):

The Base Cases

Three checks run before any partitioning happens, and they're worth doing in this specific order, since each one is cheaper than the next and can short-circuit the more expensive recursive work below it.

Length mismatch: if len(A) != len(B), return False immediately. Nothing else needs checking.

Exact match: if A == B, return True. Zero swaps is a legitimate scramble, and this also happens to be the natural base case that ends the recursion once a partition has been narrowed down to matching single characters.

Anagram pruning: if sorted(A) != sorted(B), return False. This one is worth sitting with, because it's not obviously necessary the way the first two checks are; it's an optimization built on a real property of the problem. Swapping the two children of a node in the scramble tree rearranges characters, but it can never create or destroy them, and it can never change how many of each character exist. So if A and B don't contain the same multiset of characters, no sequence of swaps, at any level of the tree, could ever turn one into the other. Checking this early prunes off entire branches of recursion that are doomed before a single partition gets tried.

if len(A) != len(B):
    return False

if A == B:
    return True

if sorted(A) != sorted(B):
    return False

The Recursive Solution

class Solution:

    def solve(self, A, B):

        if len(A) != len(B):
            return False

        if A == B:
            return True

        if sorted(A) != sorted(B):
            return False

        n = len(A)

        for k in range(1, n):

            # No Swap
            left = self.solve(A[:k], B[:k])
            right = self.solve(A[k:], B[k:])

            if left and right:
                return True

            # Swap
            left = self.solve(A[:k], B[n - k:])
            right = self.solve(A[k:], B[:n - k])

            if left and right:
                return True

        return False

    def isScramble(self, s1, s2):
        return self.solve(s1, s2)

The swapped indexing is the detail most likely to trip you up on a first read, so it's worth spelling out explicitly. A1, the first k characters of A, has length k, so in the swap case it needs to match the last k characters of B, which is B[n-k:]. A2, the remaining n-k characters of A, needs to match whatever's left, the first n-k characters of B, which is B[:n-k]. The lengths on both sides always have to agree; only which end of B they're pulled from changes between the swap and no-swap cases.

Memoizing with a Dictionary

The recursion above re-solves identical (A, B) substring pairs across different partition branches constantly, which is the same overlapping-subproblems signal that justified memoization in every earlier chapter of this series. The most direct way to cache it is keying on the actual substrings themselves.

class Solution:

    def solve(self, A, B, memo):

        if len(A) != len(B):
            return False

        if A == B:
            return True

        if sorted(A) != sorted(B):
            return False

        key = (A, B)

        if key in memo:
            return memo[key]

        n = len(A)

        for k in range(1, n):

            # No Swap
            left = self.solve(A[:k], B[:k], memo)
            right = self.solve(A[k:], B[k:], memo)

            if left and right:
                memo[key] = True
                return True

            # Swap
            left = self.solve(A[:k], B[n - k:], memo)
            right = self.solve(A[k:], B[:n - k], memo)

            if left and right:
                memo[key] = True
                return True

        memo[key] = False
        return False

    def isScramble(self, s1, s2):
        memo = {}
        return self.solve(s1, s2, memo)

The key is the pair (A, B) itself, the actual substrings, not indices. This works correctly, but it's worth noticing what it's actually storing: two full string objects per cache entry, which is more memory than strictly necessary given that every substring here is fully determined by where it starts and how long it is.

Two Ways to Represent the Same State

Both the dictionary approach and an index-based array approach are tracking the exact same logical subproblem. They just describe the coordinates of that subproblem differently.

Dictionary approach: keys are (A, B), the substrings themselves. The length of each substring is implicit, it's just len(A) and len(B), and the starting position within the original string isn't tracked at all, because the substring itself carries all the information needed.

Array approach: coordinates are T[i][j][length], where i is the starting index into the original A, j is the starting index into the original B, and length is how long the matching substrings are. Nothing gets sliced into a new substring object; the boundaries are computed on demand as A[i : i+length] and B[j : j+length].

Dictionary:  key = (A, B)                    -> substrings carry their own length
Array:       key = (i, j, length)            -> substrings recomputed from indices

This is the same tradeoff that shows up anywhere a problem can be memoized either by value (the actual substring) or by position (indices into the original string). The array version avoids the overhead of creating and hashing new string objects on every recursive call, at the cost of needing one more dimension, length, that the dictionary version got for free by just measuring the strings it was already holding onto.

The 3D Index-Based Version

class Solution:

    def solve(self, A, B, i, j, length, T):

        if length == 1:
            return A[i] == B[j]

        if T[i][j][length] != -1:
            return T[i][j][length]

        if A[i:i + length] == B[j:j + length]:
            T[i][j][length] = 1
            return True

        if sorted(A[i:i + length]) != sorted(B[j:j + length]):
            T[i][j][length] = 0
            return False

        for k in range(1, length):

            # No Swap
            left = self.solve(A, B, i, j, k, T)
            right = self.solve(A, B, i + k, j + k, length - k, T)

            if left and right:
                T[i][j][length] = 1
                return True

            # Swap
            left = self.solve(A, B, i, j + length - k, k, T)
            right = self.solve(A, B, i + k, j, length - k, T)

            if left and right:
                T[i][j][length] = 1
                return True

        T[i][j][length] = 0
        return False

    def isScramble(self, s1, s2):

        n = len(s1)

        if n != len(s2):
            return False

        T = [
            [
                [-1] * (n + 1)
                for _ in range(n)
            ]
            for _ in range(n)
        ]

        return self.solve(s1, s2, 0, 0, n, T)

T uses three sentinel values: -1 for not yet computed, 0 for False, and 1 for True, since a plain boolean can't represent "haven't checked this yet" the way -1 can.

The swap indexing needs the same care here that it needed in the plain recursive version, just expressed through index arithmetic instead of slicing. For a split at k within a range of length, the left partition has length k and the right partition has length length - k. In the swap case, the left partition of A needs to match against a piece of B starting at j + length - k, that offset is what places it at the end of the current B range rather than the start. The right partition of A matches against B starting right at j, the front of the range.

Quick Revision

Scrambled String
       |
Recursive partitioning
       |
MCM / Interval DP pattern
       |
Try k = 1 to n-1
       |
       +-----------------+
       |                 |
    No Swap            Swap
       |                 |
 A1 -> B1             A1 -> B2
 A2 -> B2             A2 -> B1
       |                 |
       +------ OR -------+
                |
             True/False

Base cases, in order:
  len(A) != len(B)         -> False
  A == B                   -> True
  sorted(A) != sorted(B)   -> False (anagram pruning)

Memoization:
  Dictionary: key = (A, B)
  Array:      T[i][j][length], sentinels -1/0/1

What You Now Understand

MCM tells you where to partition. It's the scrambling rule specifically, the choice between matching halves in order or swapped, that tells you how the two sides are allowed to correspond once you've split. That's the part genuinely new to this problem: an extra binary decision at every partition point, checked as an OR across two different pairings rather than a single fixed combination the way MCM and Palindrome Partitioning had.

The other genuinely new idea here is the length dimension in the index-based memoization. Boolean Parenthesization needed one extra dimension, isTrue, because a single count wasn't enough information for a subproblem. Scrambled String needs one extra dimension, length, because tracking a substring by its starting position alone isn't sufficient, you also need to know how far it extends, once you stop carrying that information implicitly inside an actual sliced-out string.

Coin Change I: When the Default Value Can Break Everything

Nishant Gaurav — Thu, 08 Oct 2026 12:30:00 +0000

Coin Change II counts ways. Coin Change I asks a different question: what is the minimum number of coins needed to make a given amount?

The choice structure is identical. Unbounded, same-row TAKE, previous-row SKIP. Two things change: + becomes min(...) + 1, and the initialisation needs careful thought because the default value for an impossible state can no longer be zero.

That second point is where most people get confused on this problem. This chapter addresses it directly.

The Problem

coins  = [1, 2, 3]
amount = 5

Some combinations:
  2 + 3          → 2 coins
  1 + 1 + 3      → 3 coins
  1 + 2 + 2      → 3 coins
  1 + 1 + 1 + 2  → 4 coins

Minimum = 2

Same coins as Coin Change II. Same amount. But instead of counting four ways, you want the one that uses the fewest coins.

Why the Initialisation Is Different

In Coin Change II, the table stored counts. A count of zero meant "zero ways to make this amount," which was a valid meaningful answer. And T[i][0] = 1 because there is one way to make amount zero: choose nothing.

Here the table stores the minimum number of coins. Zero means "zero coins needed," which is the correct answer for amount zero. But for amounts that are genuinely impossible to make with the available coins, you can't store zero — that would look like "zero coins needed," which is wrong. You need a sentinel value that means "this state is unreachable."

That sentinel is a very large number, conventionally called INF.

When min() compares a real answer against INF, INF loses and gets ignored. That's its entire purpose.

Why `INF = 231 - 2` and Not `231 - 1`

When you TAKE a coin, the transition adds 1:

1 + T[i][j - coins[i-1]]

If T[i][j - coins[i-1]] is 2**31 - 1 (the maximum integer), adding 1 causes integer overflow in languages like C++ and Java. The result wraps around to a negative number, which then looks like a valid minimum — a completely silent wrong answer.

Using 2**31 - 2 keeps it one step back:

1 + (2**31 - 2) = 2**31 - 1

Still a huge number, still loses to any real answer in min(), but doesn't overflow.

In Python, integers don't overflow, so float('inf') works fine. But knowing why the -1 is there matters if you're writing this in any other language.

The DP State

T[i][j] = minimum coins needed to make amount j
           using the first i coins

Initialisation in Three Parts

Amount zero: Zero coins needed regardless of which coins are available.

for i in range(n + 1):
    T[i][0] = 0

No coins available (row 0): Every positive amount is impossible.

# T[0][j] = INF for all j > 0
# Already handled if table is initialised to INF

First coin row (row 1): This needs its own loop. With only the first coin available, an amount is reachable only if it's exactly divisible by that coin.

for j in range(1, amount + 1):
    if j % coins[0] == 0:
        T[1][j] = j // coins[0]
    else:
        T[1][j] = INF

For example, with coins[0] = 3:

Amount: 0   1    2    3    4    5    6    7    8    9
Coins:  0  INF  INF   1   INF  INF   2   INF  INF   3

Amount 3 needs 1 coin. Amount 6 needs 2. Amount 1, 2, 4, 5, 7, 8 are impossible with only coin 3.

The Transition

When the coin fits (coins[i-1] <= j):

T[i][j] = min(
    1 + T[i][j - coins[i-1]],   # TAKE: same row + 1 coin
    T[i-1][j]                    # SKIP: previous row
)

The +1 counts the coin being taken. The same-row reference allows taking the same coin again.

When the coin doesn't fit:

T[i][j] = T[i-1][j]   # only SKIP

The Operation Table

Across the Unbounded family, the operation is the only thing that varies:

Problem	Goal	Operation
Rod Cutting	Maximum profit	`max(take, skip)`
Coin Change II	Count ways	`take + skip`
Coin Change I	Minimum coins	`min(1 + take, skip)`

The +1 in Coin Change I is because taking a coin costs one coin. The 1 + is absent in Rod Cutting and Coin Change II because they don't count individual items used.

The Complete Code

class Solution:

    def coinChange(self, coins, amount):

        n = len(coins)

        # INF represents an impossible/unreachable state.
        # Using 2**31 - 2 instead of 2**31 - 1 so that
        # 1 + INF doesn't overflow in other languages.
        # In Python, float('inf') also works.
        INF = 2**31 - 2

        # T[i][j] = minimum coins to make amount j
        # using first i coins.
        # Start everything as INF — unreachable by default.
        T = [[INF] * (amount + 1) for _ in range(n + 1)]

        # Amount 0 needs 0 coins — for every row
        for i in range(n + 1):
            T[i][0] = 0

        # First coin row: only reachable if amount
        # is exactly divisible by coins[0]
        for j in range(1, amount + 1):
            if j % coins[0] == 0:
                T[1][j] = j // coins[0]
            else:
                T[1][j] = INF

        # Fill remaining rows
        for i in range(2, n + 1):
            for j in range(1, amount + 1):

                if coins[i - 1] <= j:
                    # TAKE: same row (coin can be reused), add 1 coin
                    # SKIP: previous row
                    # min() because we want fewest coins
                    T[i][j] = min(
                        1 + T[i][j - coins[i - 1]],
                        T[i - 1][j]
                    )
                else:
                    # Coin too large — only skip
                    T[i][j] = T[i - 1][j]

        # If still INF, the amount is impossible
        if T[n][amount] == INF:
            return -1

        return T[n][amount]

The final check if T[n][amount] == INF: return -1 handles the case where no combination of coins can make the target amount. LeetCode's Coin Change problem expects -1 for this case.

One Correction Worth Keeping in Your Notes

An empty coin array with a positive amount does not mean "infinite ways." It means "impossible." There are zero ways, and the minimum number of coins is undefined — represented as INF. The confusion comes from mixing up Count of Subsets thinking (where T[i][0] = 1 represents the empty combination) with this problem (where T[i][0] = 0 represents zero coins needed and INF represents unreachable).

These are different kinds of "nothing."

Quick Revision

T[i][j] = minimum coins to make amount j using first i coins

Initialisation:
  Everything starts as INF
  T[i][0] = 0          (amount 0 → 0 coins)
  T[1][j] = j//coins[0] if j % coins[0] == 0, else INF

Transition:
  if coins[i-1] <= j:
    T[i][j] = min(1 + T[i][j-coins[i-1]], T[i-1][j])
  else:
    T[i][j] = T[i-1][j]

Final check:
  if T[n][amount] == INF: return -1

Why INF = 2**31 - 2:
  1 + INF must not overflow → use INF - 1 as sentinel

What You Now Understand

Coin Change I completes the core Unbounded Knapsack problem family. Three problems, one transition direction, three different operations: max, +, min(...) + 1. The initialisation is the part that actually differs meaningfully between them, because it depends on what the table stores and what "impossible" means in each context.

The next chapter moves to a different DP pattern entirely: Longest Common Subsequence. The choice diagram changes, the table dimensions change, but the same fundamental approach from Chapter 1 applies: understand the choices, find the base case, write the recursion, then build the table.

Boolean Parenthesization: The MCM Skeleton, Counting Instead of Minimising

Nishant Gaurav — Thu, 08 Oct 2026 12:30:00 +0000

Boolean Parenthesization: The MCM Skeleton, Counting Instead of Minimising

Matrix Chain Multiplication had matrices and multiplication costs. Palindrome Partitioning swapped that for a string and a +1 per cut. Boolean Parenthesization keeps the same skeleton again, but this time the combining step gets genuinely more involved, because the answer isn't a single number anymore, it's two: how many ways to reach True, and how many ways to reach False.

The Problem

Given a Boolean expression made of T, F, and the operators &, |, ^, count how many distinct ways you can parenthesize it so the whole thing evaluates to True.

s = T | F & T

Two valid parenthesizations:
  (T | F) & T   → evaluates to True
  T | (F & T)   → evaluates to True

Answer: 2

This isn't asking whether a True evaluation exists. It's asking how many structurally different ways of grouping the expression land on True.

Recognising the MCM Pattern

The same four signals from the MCM chapter show up here. There's a sequence you can partition (the expression). A minimum, or in this case a count, is being asked for. Multiple partition points are possible, one for each operator in the string.

Expression:       T | F & T
Partitions:       T | (F & T)
                   (T | F) & T
Counting answer:  yes
Multiple k:       yes

The same (i, j, k) structure applies, with i and j marking the boundaries of the current substring and k marking where you split it. The difference shows up almost immediately once you try to define what solve(i, j) should even return.

Why One Number Isn't Enough

In MCM, solve(i, j) returns a single number, the minimum cost. In Palindrome Partitioning, solve(i, j) also returns a single number, the minimum cuts. Here, a single number breaks down almost immediately once you think through what combining two sides actually requires.

Take the XOR operator. Left ^ Right evaluates to True in exactly two situations: Left is True and Right is False, or Left is False and Right is True.

True ^ False = True
False ^ True = True

To count the ways Left ^ Right can be True, you need to know how many ways Left can be True, how many ways Left can be False, how many ways Right can be True, and how many ways Right can be False, all four, not just one of them. A solve(i, j) that only tracks "minimum cost" or "cuts" has nowhere to put that information.

So the state grows by one dimension. Instead of solve(i, j), it's solve(i, j, isTrue):

solve(s, i, j, isTrue)

isTrue = True  → count of ways s[i..j] evaluates to True
isTrue = False → count of ways s[i..j] evaluates to False

Every call to solve for a given (i, j) range actually needs both variants computed, because the combining step for whichever operator sits at the split point needs both the True count and the False count from each side.

The Base Cases

Two conditions end the recursion, and they mirror the MCM and Palindrome Partitioning base cases closely, just adjusted for the extra isTrue flag.

i > j: An invalid, empty range. Nothing to evaluate. Return 0.

i == j: A single operand remains, either T or F. Whether this counts toward the answer depends on what isTrue is asking for.

if i > j:
    return 0

if i == j:
    if isTrue:
        return 1 if s[i] == 'T' else 0
    else:
        return 1 if s[i] == 'F' else 0

If isTrue is True and the single character is literally T, there's exactly one way to make this range True, itself. If the character is F instead, there are zero ways to make it True. The isTrue = False branch mirrors this exactly, checking for F instead.

Finding k, Operators Only

Just like MCM splits between matrices and Palindrome Partitioning splits between characters, Boolean Parenthesization splits at operator positions. Operands and operators alternate in the string, so k has to land specifically on an operator index, never on a T or F.

Index:  0   1   2   3   4
Value:  T   |   F   &   T

The operators sit at odd indices, 1 and 3. Stepping by 2 starting from i + 1 walks across exactly those positions:

for k in range(i + 1, j, 2):

Each k splits the expression into a left substring s[i..k-1], the operator s[k], and a right substring s[k+1..j].

The Combining Step

This is where the extra dimension actually pays off. For each k, both sides get solved for both True and False:

leftTrue  = solve(s, i, k - 1, True)
leftFalse = solve(s, i, k - 1, False)

rightTrue  = solve(s, k + 1, j, True)
rightFalse = solve(s, k + 1, j, False)

Compare this against the single tempAns line from Palindrome Partitioning:

MCM:                    tempAns = left + right + arr[i-1]*arr[k]*arr[j]
Palindrome Partitioning: tempAns = left + right + 1
Boolean Parenthesization: four separate values, combined differently per operator

There's no single tempAns line here, because the combination depends entirely on which operator sits at k. Each operator has its own truth table, and each truth table tells you exactly which pairs of left and right outcomes multiply together to contribute toward True, and which contribute toward False.

AND (&): True only when both sides are True.

target True:  leftTrue * rightTrue
target False: everything else = (leftTrue * rightFalse) + (leftFalse * rightTrue) + (leftFalse * rightFalse)

OR (|): False only when both sides are False.

target True:  everything else = (leftTrue * rightTrue) + (leftTrue * rightFalse) + (leftFalse * rightTrue)
target False: leftFalse * rightFalse

XOR (^): True only when the sides disagree.

target True:  (leftTrue * rightFalse) + (leftFalse * rightTrue)
target False: (leftTrue * rightTrue) + (leftFalse * rightFalse)

In every case, multiplication combines two independent counts (this is the counting principle: if there are a ways to make the left side a certain value and b ways to make the right side a certain value, there are a * b ways to combine them into that pair), and addition combines multiple mutually exclusive ways of reaching the same target across different operand combinations.

The Recursive Solution

class Solution:

    def solve(self, s, i, j, isTrue):

        if i > j:
            return 0

        if i == j:
            if isTrue:
                return 1 if s[i] == 'T' else 0
            else:
                return 1 if s[i] == 'F' else 0

        ans = 0

        for k in range(i + 1, j, 2):

            leftTrue = self.solve(s, i, k - 1, True)
            leftFalse = self.solve(s, i, k - 1, False)

            rightTrue = self.solve(s, k + 1, j, True)
            rightFalse = self.solve(s, k + 1, j, False)

            op = s[k]

            if op == '&':
                if isTrue:
                    ans += leftTrue * rightTrue
                else:
                    ans += (
                        leftTrue * rightFalse
                        + leftFalse * rightTrue
                        + leftFalse * rightFalse
                    )

            elif op == '|':
                if isTrue:
                    ans += (
                        leftTrue * rightTrue
                        + leftTrue * rightFalse
                        + leftFalse * rightTrue
                    )
                else:
                    ans += leftFalse * rightFalse

            elif op == '^':
                if isTrue:
                    ans += (
                        leftTrue * rightFalse
                        + leftFalse * rightTrue
                    )
                else:
                    ans += (
                        leftTrue * rightTrue
                        + leftFalse * rightFalse
                    )

        return ans

    def countWays(self, s):
        return self.solve(s, 0, len(s) - 1, True)

countWays calls solve once, over the full string, asking specifically for the True count, since that's the actual question the problem is asking.

A Small Dry Run

s = T ^ F
Index:  0   1   2
        T   ^   F

The only operator sits at k = 1, so the left substring is s[0..0] = "T" and the right substring is s[2..2] = "F".

Left (T): leftTrue = 1 (it's literally T), leftFalse = 0.

Right (F): rightTrue = 0, rightFalse = 1 (it's literally F).

Combining with XOR's target-True formula:

target True = leftTrue * rightFalse + leftFalse * rightTrue
            = (1 * 1) + (0 * 0)
            = 1

One way to make T ^ F evaluate to True, which checks out, since there's only one possible parenthesization for a two-operand expression in the first place, and it does evaluate to True.

MCM vs Palindrome Partitioning vs Boolean Parenthesization

	MCM	Palindrome Partitioning	Boolean Parenthesization
Input	Dimension array	String	Boolean expression string
State	`solve(i, j)`	`solve(i, j)`	`solve(i, j, isTrue)`
`k` loop	`range(i, j)`	`range(i, j)`	`range(i+1, j, 2)`, operators only
Left/right subproblems	One value each	One value each	Two values each (True count, False count)
Combining step	`left + right + arr[i-1]arr[k]arr[j]`	`left + right + 1`	Per-operator truth table, multiply and add
Aggregation across k	`min`	`min`	`+=` (sum across all valid splits)
Answer represents	A minimum cost	A minimum cut count	A count of valid parenthesizations

The pattern holds across all three: boundaries i and j, a loop over valid split points k, subproblems solved on both sides, and a combination step that's specific to the problem. What changes each time is what the state actually needs to track, and how the two sides get combined once you have them. MCM and Palindrome Partitioning could get away with a single value per subproblem because they were optimizing one number. Boolean Parenthesization needs both True and False counts, because the operator's truth table decides which cross-combinations of the two sides actually matter.

Quick Revision

solve(i, j, isTrue) = number of ways s[i..j] evaluates to isTrue

Base cases:
  if i > j: return 0
  if i == j: return 1 if s[i] matches isTrue, else 0

Transition:
  for k in range(i+1, j, 2):   # operators only
    leftTrue, leftFalse   = solve(i, k-1, True), solve(i, k-1, False)
    rightTrue, rightFalse = solve(k+1, j, True), solve(k+1, j, False)
    combine using s[k]'s truth table, add to ans

Initial call: solve(0, n-1, True)

The change from MCM and Palindrome Partitioning:
  state grows from (i, j) to (i, j, isTrue)
  each subproblem needs both True and False counts
  combining step is a truth table per operator, not a single formula

What You Now Understand

Boolean Parenthesization keeps the exact same partitioning skeleton as MCM and Palindrome Partitioning, boundaries, a split point, subproblems on both sides, but it's the first problem in this family where a single number per subproblem genuinely isn't enough. The moment an operator like XOR needs to know both how a side can be True and how it can be False to figure out what the combination produces, the state has to grow to carry both. That's the real lesson here: the skeleton doesn't change, but the shape of what each subproblem needs to return depends entirely on what the combining step at the top actually requires.

The next chapter takes this same recursive solution and adds memoization to it, the same reasoning as before, except now the cache has to be keyed on three values instead of two, (i, j, isTrue), using either a dictionary or a structured 3D table.

Palindrome Partitioning: The MCM Skeleton With a New `tempAns`

Nishant Gaurav — Wed, 07 Oct 2026 12:30:00 +0000

Matrix Chain Multiplication had matrices and multiplication costs. Palindrome Partitioning has a string and cuts. The problems look nothing alike. But once you map the structure, the skeleton is identical and only tempAns changes.

The Problem

Given a string, partition it so that every substring in the partition is a palindrome. Find the minimum number of cuts needed.

s = "NITIK"

Trivial partition:  N | I | T | I | K  → 4 cuts (valid but not minimal)
Optimal partition:  N | ITI | K        → 2 cuts

N   → palindrome ✓
ITI → palindrome ✓
K   → palindrome ✓

Answer: 2

Every individual character is a palindrome, so you can always cut the string into single characters. But that's the worst case. You want to find where cutting fewer times still gives all palindromes.

Recognising the MCM Pattern

From Chapter 1, the four signals are: array or string, can be partitioned, minimum answer needed, multiple partition points possible.

String:          NITIK
Partitions:      N | ITIK
                 NI | TIK
                 NIT | IK
                 NITI | K
Minimum answer:  yes
Multiple k:      yes

All four signals are present. This is an MCM problem.

The same (i, j, k) structure applies. i is the left boundary, j is the right boundary, k is the split point. solve(i, j) is the minimum cuts for s[i..j].

The Base Cases

Two things can end the recursion early.

i >= j: A single character or an empty range. One character is always a palindrome. No cuts needed. Return 0.

The entire substring s[i..j] is already a palindrome: No need to partition it at all. Return 0.

if i >= j:
    return 0

if isPalindrome(s, i, j):
    return 0

The isPalindrome check is an extra base case that doesn't exist in MCM. It's a short-circuit: if the current range is already palindromic, don't cut it further.

The `tempAns` Line

After the base cases, try every k from i to j-1. Split the string at k and compute the cost of each partition.

solve(i, k)    → minimum cuts for left substring s[i..k]
solve(k+1, j)  → minimum cuts for right substring s[k+1..j]
+1             → the cut at position k that separates the two halves

tempAns = solve(i, k) + solve(k + 1, j) + 1
ans = min(ans, tempAns)

Compare with MCM:

MCM:                  solve(i,k) + solve(k+1,j) + arr[i-1]*arr[k]*arr[j]
Palindrome:           solve(i,k) + solve(k+1,j) + 1

The +1 replaces the multiplication cost. Everything else is the same.

The Helper Function

def isPalindrome(s, i, j):
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

This runs in O(n) per call. For each (i, j) pair and each value of k, isPalindrome is called on the initial range once. It's not called on each subproblem — the base case check only applies to the top-level call for each (i, j).

The Recursive Solution

class Solution:

    def isPalindrome(self, s, i, j):
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    def solve(self, s, i, j):

        # Base case: single char or empty range
        if i >= j:
            return 0

        # Short-circuit: no cuts needed if already palindrome
        if self.isPalindrome(s, i, j):
            return 0

        ans = float('inf')

        for k in range(i, j):
            # Cut at k: left + right + 1 cut
            tempAns = (
                self.solve(s, i, k)
                + self.solve(s, k + 1, j)
                + 1
            )
            ans = min(ans, tempAns)

        return ans

    def minCut(self, s):
        return self.solve(s, 0, len(s) - 1)

Adding Memoization

Same reasoning as MCM. The state is (i, j). Initialise with -1. Check before computing, store after.

class Solution:

    def isPalindrome(self, s, i, j):
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    def minCut(self, s):

        n = len(s)
        T = [[-1] * n for _ in range(n)]

        def solve(i, j):

            if i >= j:
                return 0

            if self.isPalindrome(s, i, j):
                return 0

            # Return stored answer if already computed
            if T[i][j] != -1:
                return T[i][j]

            ans = float('inf')

            for k in range(i, j):

                # Use cached values where available
                left  = T[i][k]   if T[i][k]   != -1 else solve(i, k)
                right = T[k+1][j] if T[k+1][j] != -1 else solve(k+1, j)

                if T[i][k]   == -1: T[i][k]   = left
                if T[k+1][j] == -1: T[k+1][j] = right

                tempAns = 1 + left + right
                ans = min(ans, tempAns)

            T[i][j] = ans
            return ans

        return solve(0, n - 1)

MCM vs Palindrome Partitioning

	MCM	Palindrome Partitioning
Input	Dimension array	String
`solve(i,j)` means	Min multiplication cost	Min cuts
`k` loop	`range(i, j)`	`range(i, j)`
Left subproblem	`solve(i, k)`	`solve(i, k)`
Right subproblem	`solve(k+1, j)`	`solve(k+1, j)`
`tempAns`	`left + right + arr[i-1]arr[k]arr[j]`	`left + right + 1`
Extra base case	None	`isPalindrome(s, i, j)`
Aggregation	`min`	`min`
Memoised state	`(i, j)`	`(i, j)`

The rows that differ: tempAns and the extra palindrome base case. Every other row is identical.

Quick Revision

solve(i, j) = minimum cuts for s[i..j]

Base cases:
  if i >= j: return 0
  if isPalindrome(s, i, j): return 0

Transition:
  for k in range(i, j):
    tempAns = solve(i,k) + solve(k+1,j) + 1
    ans = min(ans, tempAns)

Memoize: T[i][j], initialised to -1

Initial call: solve(0, n-1)

The only change from MCM:
  tempAns uses +1 instead of arr[i-1]*arr[k]*arr[j]
  Extra isPalindrome base case

What You Now Understand

Palindrome Partitioning is MCM with a simpler tempAns. The combining cost of splitting a string at position k is just +1 — the single cut that divides the two halves. The isPalindrome check is an optimisation that short-circuits the recursion when the current range needs no further cutting.

The next chapter applies the same skeleton to Boolean Parenthesization, where the tempAns becomes more involved: instead of counting cuts or multiplications, you're counting how many ways to parenthesise a boolean expression so that it evaluates to True. The structure is the same. The combination logic is where things get interesting.

Coin Change II: Counting Ways With Unlimited Coins

Nishant Gaurav — Wed, 07 Oct 2026 12:30:00 +0000

Rod Cutting asked: what's the maximum profit? Coin Change II asks: how many ways can you reach a target amount? The choice structure is the same. The transition direction is the same. Two things change: max() becomes +, and the initialisation needs one careful adjustment.

If you've been following the series, this chapter should feel like a small variation on something familiar rather than a new problem entirely.

The Problem

Given a list of coin denominations and a target amount, count the number of distinct combinations of coins that sum to that amount. Each coin can be used any number of times.

coins  = [1, 2, 5]
amount = 5

Ways to make 5:
  5
  2 + 2 + 1
  2 + 1 + 1 + 1
  1 + 1 + 1 + 1 + 1

Answer = 4

Note that 2 + 2 + 1 and 1 + 2 + 2 count as the same combination. Order doesn't matter here — it's combinations, not permutations.

Where It Sits in the Pattern

The choice diagram is the standard TAKE / SKIP fork. And since the same coin can be used multiple times, it's Unbounded Knapsack. Since you're counting how many ways rather than finding a maximum, the operation is + instead of max().

Here's how the operation changes across the problems you've seen so far:

Problem	Question	Operation
0/1 Knapsack	Maximum value	`max()`
Subset Sum	Possible or not	`or`
Count of Subsets	How many ways (each item once)	`+`
Rod Cutting	Maximum profit	`max()`
Coin Change II	How many ways (unlimited use)	`+`

Coin Change II looks like Count of Subsets, but with one critical difference in the TAKE branch.

The Difference From Count of Subsets

Count of Subsets (from Chapter 4) also counted ways using +. But each element could only be used once, so TAKE moved to the previous row.

Coin Change II allows unlimited use, so TAKE stays on the same row.

Count of Subsets (0/1):
T[i][j] = T[i-1][j - arr[i-1]]   ← previous row
         + T[i-1][j]

Coin Change II (Unbounded):
T[i][j] = T[i][j - coins[i-1]]   ← same row
         + T[i-1][j]

One index. Completely different behaviour.

The DP State

T[i][j] = number of ways to make amount j
           using the first i coins

T[3][5] means: using only the first three coin denominations, how many combinations make 5?

Final answer: T[n][amount].

Initialisation

Two boundaries to think through.

No coins available (i = 0): You can't make any positive amount with zero coins. T[0][j] = 0 for all j > 0. This is already handled by initialising the table to zero.

Amount zero (j = 0): There is exactly one way to make amount zero: choose nothing. The empty combination. So T[i][0] = 1 for every i.

for i in range(n + 1):
    T[i][0] = 1

This is different from Count of Subsets in Chapter 4, where you initialised only T[0][0] = 1 and let the transition handle zeros in the array. Here there are no zero-valued coins to worry about (coin denominations are always positive), so initialising the entire first column to 1 is safe and correct.

The Transition

When the coin fits (coins[i-1] <= j):

T[i][j] = T[i][j - coins[i-1]]   # TAKE: same row
         + T[i-1][j]              # SKIP: previous row

We add because we're counting. Ways from TAKE plus ways from SKIP gives total ways.

When the coin doesn't fit (coins[i-1] > j):

T[i][j] = T[i-1][j]   # only SKIP

The Complete Code

class Solution:

    def change(self, amount, coins):

        n = len(coins)

        # T[i][j] = number of ways to make amount j
        # using the first i coins
        T = [[0] * (amount + 1) for _ in range(n + 1)]

        # Amount 0 has exactly one combination: choose nothing
        for i in range(n + 1):
            T[i][0] = 1

        for i in range(1, n + 1):
            for j in range(1, amount + 1):

                if coins[i - 1] <= j:
                    # TAKE: same row (unbounded — coin can be used again)
                    # SKIP: previous row
                    # Add because we are counting ways
                    T[i][j] = (
                        T[i][j - coins[i - 1]]
                        + T[i - 1][j]
                    )
                else:
                    # Coin too large — only SKIP
                    T[i][j] = T[i - 1][j]

        return T[n][amount]

A Dry Run

For coins = [1, 2, 5], amount = 5:

After filling the table with coin 1 (row 1), every amount from 1 to 5 has exactly 1 way (all ones). After adding coin 2 (row 2), each amount gains ways that combine 2s with 1s. By the time coin 5 (row 3) is added, T[3][5] captures all four combinations.

The key cell to trace: T[2][4] with coins [1, 2].

coins[1] = 2, j = 4
2 <= 4 → fits

T[2][4] = T[2][4-2] + T[1][4]
        = T[2][2]   + T[1][4]

T[2][2] is at the same row, meaning: how many ways to make 2 using coins [1, 2]? That's 2 (either 2 or 1+1). T[1][4] is using only coin 1 to make 4: exactly 1 way (1+1+1+1). So T[2][4] = 2 + 1 = 3. Three ways to make 4 using coins [1, 2]: 2+2, 2+1+1, 1+1+1+1.

Three Things to Keep Straight

Why +? You're counting ways. Ways from TAKE plus ways from SKIP.

Why same row on TAKE? Unlimited coin use. Same coin available after picking it.

Why T[i][0] = 1? Amount zero has one valid combination: pick nothing.

Quick Revision

T[i][j] = number of ways to make amount j using first i coins

Initialisation:
  T[i][0] = 1 for all i     (empty combination makes 0)
  T[0][j] = 0 for all j > 0 (no coins, no ways)

Transition:
  if coins[i-1] <= j:
    T[i][j] = T[i][j-coins[i-1]] + T[i-1][j]
  else:
    T[i][j] = T[i-1][j]

Key: same row + + = Unbounded counting problem

What You Now Understand

Coin Change II is Count of Subsets made unbounded. The + comes from counting. The same-row TAKE comes from unlimited use. The T[i][0] = 1 initialisation comes from the empty combination being a valid answer for amount zero.

Chapter 10 covers Coin Change I, where the question shifts again: instead of counting how many ways, you want the minimum number of coins. The transition flips from + to min(), and the initialisation needs a different starting value for the same reason Count of Subsets used None instead of False — the default value can't be a valid answer.

Rod Cutting: Unbounded Knapsack With a Different Label on the Inputs

Nishant Gaurav — Tue, 06 Oct 2026 12:30:00 +0000

Chapter 7 introduced Unbounded Knapsack and ended with a promise: every problem in the unbounded family inherits the same structure, just with a different question. Rod Cutting is the first of those problems, and it's a good one to start with because the mapping from Knapsack to Rod Cutting is clean and direct.

Once you see the mapping, the code practically writes itself.

The Problem

You have a rod of length n. For every possible piece length, there's a price you can sell it for.

price = [1, 5, 8, 9]

Length 1 → price 1
Length 2 → price 5
Length 3 → price 8
Length 4 → price 9

Cut the rod into pieces in whatever combination maximises total profit.

For a rod of length 4, some options:

Don't cut at all:    length 4           → profit 9
Cut into two halves: 2 + 2              → profit 5 + 5 = 10
Cut three pieces:    1 + 1 + 2          → profit 1 + 1 + 5 = 7
Cut four pieces:     1 + 1 + 1 + 1      → profit 1 + 1 + 1 + 1 = 4

The best option here is 2 + 2 with profit 10.

One thing to notice: some versions of this problem give you both a length array and a price array. Others give only price, with the lengths implied as [1, 2, 3, ..., n]. When the length array isn't given, just construct it as range(1, n+1) where n = len(price). There's nothing more to it.

Why This Is an Unbounded Knapsack Problem

For each available piece length, you decide: use this length or don't. That's the TAKE / SKIP structure of Knapsack.

And the same piece length can be used multiple times. 2 + 2 uses the length-2 piece twice. 1 + 1 + 1 + 1 uses the length-1 piece four times. There's no restriction on repetition.

That's Unbounded Knapsack.

The variable names just change:

Unbounded Knapsack    →    Rod Cutting

weight                →    piece length
value                 →    price
capacity              →    rod length
maximum value         →    maximum profit

The DP Table

T[i][j] = maximum profit using the first i piece lengths
           for a rod of length j

Rows represent which piece lengths are available. Columns represent the rod length being considered.

          Rod Length (j) →
          0   1   2   3   4
Length
  0       0   0   0   0   0
  1       0   ?   ?   ?   ?
  2       0   ?   ?   ?   ?
  3       0   ?   ?   ?   ?
  4       0   ?   ?   ?   ?

Base cases are the same as always: no piece lengths available means profit is 0, rod of length 0 means profit is 0. The whole table initialises to zero.

The Fit Condition: `if i <= j`

Before deciding TAKE or SKIP, you need to check whether the current piece actually fits in the current rod length.

Here i is the piece length and j is the rod length. So the condition is:

if i <= j:
    # piece fits — TAKE or SKIP
else:
    # piece too long — only SKIP

This is not anything new. It's the same fit check as in Knapsack (if wt[i-1] <= j). The difference is that in Rod Cutting, i is both the row index and the piece length. Since lengths go 1, 2, 3, ..., n and the row index goes 1, 2, 3, ..., n, the piece length at row i is simply i. So wt[i-1] from Knapsack becomes just i.

The Transition

When the piece fits:

T[i][j] = max(
    price[i-1] + T[i][j-i],   # TAKE: same row (unbounded)
    T[i-1][j]                  # SKIP: previous row
)

The TAKE branch subtracts i from j (the piece length from the rod length) and stays at row i. Staying at row i means the same piece length is still available, so it can be picked again. That's the unbounded behaviour from Chapter 7.

When the piece doesn't fit:

T[i][j] = T[i-1][j]   # only SKIP is possible

A Small Dry Run

For price = [1, 5, 8, 9], consider i = 2, j = 4:

2 <= 4 → piece fits

T[2][4] = max(
    price[1] + T[2][4-2],
    T[1][4]
)
= max(
    5 + T[2][2],
    T[1][4]
)

T[2][2] is at the same row i = 2. That cell can itself pick another length-2 piece since 2 <= 2. So 2 + 2 is a valid selection. The unbounded behaviour is visible here in a concrete cell computation.

The Complete Code

class Solution:

    def cutRod(self, price):

        n = len(price)

        # T[i][j] = max profit using first i piece lengths
        # for a rod of length j.
        # Initialised to 0 — handles both base cases.
        T = [[0] * (n + 1) for _ in range(n + 1)]

        # i is both the row index and the piece length
        # (lengths are 1-indexed: 1, 2, ..., n)
        for i in range(1, n + 1):
            for j in range(1, n + 1):

                if i <= j:
                    # Piece fits — TAKE or SKIP
                    T[i][j] = max(
                        price[i - 1] + T[i][j - i],  # TAKE: stay at row i
                        T[i - 1][j]                   # SKIP: move to row i-1
                    )
                else:
                    # Piece too long — only SKIP
                    T[i][j] = T[i - 1][j]

        # Answer: all piece lengths considered, full rod length
        return T[n][n]

Compare this with the Unbounded Knapsack code from Chapter 7. The only structural difference is if i <= j instead of if wt[i-1] <= j, and T[i][j-i] instead of T[i][j-wt[i-1]]. Both simplifications happen because piece length at row i is just i.

The Pattern Connection

Quick Revision

The mapping:

Knapsack weight    → piece length (i)
Knapsack value     → price[i-1]
Knapsack capacity  → rod length (j)

The fit condition:

if i <= j:    # piece length fits in rod length

The transition:

T[i][j] = max(
    price[i-1] + T[i][j-i],  # TAKE: same row (unbounded)
    T[i-1][j]                 # SKIP: previous row
)

When length array isn't given:

lengths are implicitly [1, 2, 3, ..., n]
where n = len(price)

What You Now Understand

Rod Cutting is Unbounded Knapsack with renamed variables. The fit condition i <= j is just checking whether the piece is short enough to fit in the remaining rod. The TAKE branch stays on the same row because the same piece length can be used again.

Chapter 9 continues the Unbounded family with Coin Change I: instead of maximising profit, you're minimising the number of coins to reach a target amount. The choice structure stays the same. The operation changes from max to min, and the initialisation needs one careful adjustment because of it.

Matrix Chain Multiplication: Making the Skeleton Concrete

Nishant Gaurav — Tue, 06 Oct 2026 12:30:00 +0000

Chapter 1 introduced the MCM skeleton. This chapter fills in the one line that was left abstract: tempAns. For Matrix Chain Multiplication specifically, that line becomes the cost of multiplying two groups of matrices together after splitting the chain at position k.

Everything else — the i, j boundaries, the k loop, the recursion into both halves, the min aggregation — comes directly from Chapter 1.

The Problem

You're given an array of dimensions representing a chain of matrices.

arr = [40, 20, 30, 10, 30]

Matrix A1: 40 × 20   (arr[0] × arr[1])
Matrix A2: 20 × 30   (arr[1] × arr[2])
Matrix A3: 30 × 10   (arr[2] × arr[3])
Matrix A4: 10 × 30   (arr[3] × arr[4])

The matrices must be multiplied in order — you can't rearrange them. But you can choose where to put the parentheses, and different parenthesizations have different costs.

(A1 × A2) × (A3 × A4)
A1 × (A2 × (A3 × A4))
(A1 × (A2 × A3)) × A4

All three produce the same result matrix. But the number of scalar multiplications required is different for each. Find the parenthesization with the minimum cost.

How Matrix Multiplication Cost Works

To multiply a matrix of dimensions a × b by a matrix of dimensions b × c, you perform a × b × c scalar multiplications, and the result is a × c.

A = 40 × 20
B = 20 × 30

A × B costs: 40 × 20 × 30 = 24,000
Result: 40 × 30

This formula — arr[i-1] × arr[k] × arr[j] — becomes the combining cost in the MCM recurrence.

How the Array Represents the Matrices

This indexing is important and trips people up.

Matrix Ai has dimensions: arr[i-1] × arr[i]

A1 = arr[0] × arr[1]
A2 = arr[1] × arr[2]
A3 = arr[2] × arr[3]
A4 = arr[3] × arr[4]

If arr has n elements, there are n-1 matrices. For arr = [40, 20, 30, 10, 30] with n = 5, there are 4 matrices.

This is why the initial call is solve(1, n-1) not solve(0, n-1). The matrices are indexed 1 through n-1, not 0 through n-1.

Applying the MCM Skeleton

From Chapter 1, the skeleton is:

def solve(i, j):
    if i >= j: return 0
    ans = INF
    for k in range(i, j):
        left    = solve(i, k)
        right   = solve(k + 1, j)
        tempAns = left + right + cost(i, k, j)   ← fill this in
        ans = min(ans, tempAns)
    return ans

For Matrix Chain Multiplication, cost(i, k, j) is the cost of multiplying the result of the left group with the result of the right group.

After solve(i, k), the left group produces a matrix of dimensions arr[i-1] × arr[k].
After solve(k+1, j), the right group produces a matrix of dimensions arr[k] × arr[j].

Multiplying these two together costs: arr[i-1] × arr[k] × arr[j].

So:

tempAns = solve(i, k) + solve(k + 1, j) + arr[i-1] * arr[k] * arr[j]

That's the only line that needed to be determined. The rest was already in the skeleton.

The Full Recurrence

solve(i, j) = minimum cost to multiply matrices Ai through Aj

Base case:
  if i >= j: return 0   (one matrix or less — no multiplication needed)

Transition:
  for k in range(i, j):
    tempAns = solve(i, k) + solve(k + 1, j) + arr[i-1] * arr[k] * arr[j]
    ans = min(ans, tempAns)

The Recursive Solution

class Solution:

    def solve(self, arr, i, j):

        # Base case: one matrix or invalid range — no cost
        if i >= j:
            return 0

        ans = float('inf')

        # Try every possible split point
        for k in range(i, j):

            # Cost of left group + cost of right group + cost of combining them
            tempAns = (
                self.solve(arr, i, k)
                + self.solve(arr, k + 1, j)
                + arr[i - 1] * arr[k] * arr[j]
            )

            ans = min(ans, tempAns)

        return ans

    def matrixMultiplication(self, arr):
        n = len(arr)
        return self.solve(arr, 1, n - 1)

This works correctly but is slow. The same (i, j) pair appears in multiple branches of the recursion. For example, solve(2, 3) might be computed once when k=1 calls solve(2, 4) which calls solve(2, 3), and again from a different path. Memoization fixes this.

Adding Memoization

The state is (i, j). The table is (n × n) initialised to -1. The k loop is not part of the state — it's just how we explore all options for a given (i, j).

class Solution:

    def matrixMultiplication(self, arr):

        n = len(arr)

        # -1 = not computed yet (0 is a valid cost, so can't use 0)
        T = [[-1] * n for _ in range(n)]

        def solve(i, j):

            # Base case
            if i >= j:
                return 0

            # Return stored answer if already computed
            if T[i][j] != -1:
                return T[i][j]

            ans = float('inf')

            for k in range(i, j):

                tempAns = (
                    solve(i, k)
                    + solve(k + 1, j)
                    + arr[i - 1] * arr[k] * arr[j]
                )

                ans = min(ans, tempAns)

            T[i][j] = ans
            return ans

        return solve(1, n - 1)

The memoization check (if T[i][j] != -1) is placed before the loop. If (i, j) was already solved, return the stored answer immediately without re-running the loop.

Note: -1 is the sentinel because 0 is a valid answer (a single matrix has zero multiplication cost). The same reasoning applies here as it did in Coin Change I and Count of Subsets from the Knapsack series.

A Partial Dry Run

arr = [40, 20, 30, 10, 30]
Call: solve(1, 4)

k = 1: A1 | A2 A3 A4
  left  = solve(1, 1) = 0
  right = solve(2, 4) = ...
  cost  = arr[0] * arr[1] * arr[4] = 40 * 20 * 30 = 24,000

k = 2: A1 A2 | A3 A4
  left  = solve(1, 2) = ...
  right = solve(3, 4) = ...
  cost  = arr[0] * arr[2] * arr[4] = 40 * 30 * 30 = 36,000

k = 3: A1 A2 A3 | A4
  left  = solve(1, 3) = ...
  right = solve(4, 4) = 0
  cost  = arr[0] * arr[3] * arr[4] = 40 * 10 * 30 = 12,000

The final answer is min of tempAns across all three values of k. The recursive calls compute the internal costs. The answer for arr = [40, 20, 30, 10, 30] is 26,000.

MCM Pattern Checklist for This Problem

Question	Answer
What is `i`?	Left matrix index (1-based)
What is `j`?	Right matrix index (1-based)
Base case?	`if i >= j: return 0`
`k` range?	`range(i, j)`
Left subproblem?	`solve(i, k)`
Right subproblem?	`solve(k+1, j)`
Combining cost?	`arr[i-1] * arr[k] * arr[j]`
Aggregation?	`min`

Quick Revision

arr = dimensions array, n = len(arr), n-1 matrices
Matrix Ai = arr[i-1] × arr[i]
Initial call: solve(1, n-1)

Base case: if i >= j: return 0

Transition:
  for k in range(i, j):
    tempAns = solve(i,k) + solve(k+1,j) + arr[i-1]*arr[k]*arr[j]
    ans = min(ans, tempAns)

Memoization: T[i][j], initialised to -1
  Why -1: 0 is a valid answer (single matrix costs 0)

What You Now Understand

The MCM skeleton from Chapter 1 applied directly. The only new work was identifying that the combining cost is arr[i-1] * arr[k] * arr[j] — the cost of multiplying the result of the left group with the result of the right group. Everything else was already written.

The next chapter applies the same skeleton to Palindrome Partitioning: given a string, find the minimum number of cuts to partition it into palindromes. The tempAns changes, the base case changes slightly, and the aggregation stays min. The structure doesn't change at all.

Matrix Chain Multiplication: A New DP Pattern Built on One Question

Nishant Gaurav — Mon, 05 Oct 2026 12:30:00 +0000

The Knapsack pattern asks: should I take this item or skip it? The LCS pattern asked: do these two characters match? The MCM pattern asks something different: where should I split this?

MCM is not one problem. It's a pattern that appears across eight or more problems: Matrix Chain Multiplication, Boolean Parenthesization, Palindrome Partitioning, Egg Dropping, and others. The problems look very different from each other. But once you see the shared structure, each new problem becomes a matter of changing one or two lines inside a familiar skeleton.

This chapter is about that skeleton.

How to Recognise an MCM Problem

When you see a new problem, look for these four signals:

You're given an array or a string
You need to partition or break it somehow
You need a minimum, maximum, count, or boolean answer
Multiple partition points are possible and you don't know which is optimal

The triggering question is: can I split this problem at some position k, solve the two halves independently, and combine the results?

If yes, MCM pattern likely applies.

The Core Idea

Every MCM problem works on a range [i, j]. You pick a partition point k somewhere inside that range, solve the left half [i, k] and the right half [k+1, j] independently, then combine the two results.

i ─────────────────── j

         ↓ split at k

i ──── k │ k+1 ──── j

Since you don't know which k is optimal, you try every possible k in the range and keep the best result.

The Generic Structure

This pseudocode is the skeleton of every MCM problem. The only thing that varies between problems is what goes inside tempAns and whether you take min, max, count, or a boolean.

def solve(arr, i, j):

    # base case — smallest valid or first invalid input
    if i >= j:
        return 0

    ans = float('inf')   # or 0, or -inf, depending on the problem

    for k in range(i, j):

        left    = solve(arr, i, k)       # solve left partition
        right   = solve(arr, k + 1, j)   # solve right partition

        # combine results — THIS LINE changes per problem
        tempAns = left + right + cost(i, k, j)

        ans = min(ans, tempAns)           # or max, or +=, depending on the problem

    return ans

The structure has three parts:

The boundaries i and j: Define which portion of the array you're currently solving. In the initial call, i = 0 and j = n-1 (or n depending on the problem).

The partition loop for k in range(i, j): Try every position where the range could be split. k goes from i to j-1, never reaching j because you need at least one element on each side.

The combination tempAns: This is where the problems differ. What does it cost or produce to split at k? How do the left and right results combine? Once you answer this for a specific problem, the rest of the skeleton is already written.

[

The Recursive Tree

Every call to solve(i, j) generates two calls for each value of k. Each of those calls generates more calls. The structure looks like this:

          solve(i, j)
               |
           k = i to j-1
            /      \
           /        \
    solve(i, k)   solve(k+1, j)
         |               |
         ...             ...

The same subproblem — the same (i, j) pair — can appear through multiple paths. That's the overlapping subproblems signal from Chapter 1 of this series. When you add memoization or convert to tabulation, each (i, j) is computed only once.

Base Cases

Two questions to ask:

What is the smallest valid input? When i == j, only one element remains. This is often the base case. What should a single element return? Usually 0, because there's nothing to partition.

What is the first invalid input? When i > j, the pointers have crossed and there are no elements. This is always invalid. Return 0 or whatever the problem requires.

Which one you use depends on the problem. Some problems only need i == j. Others need to handle i > j too. But always ask both questions when designing the base case.

i ───────────── j        normal range
i === j                  one element (smallest valid)
i > j                    crossed pointers (invalid)

What Changes Between MCM Problems

The skeleton is fixed. The tempAns line is the problem. Here's what varies:

Problem	`tempAns`	Aggregation
Matrix Chain Multiplication	`left + right + arr[i-1]arr[k]arr[j]`	`min`
Palindrome Partitioning	`left + right + 1`	`min`
Boolean Parenthesization	truth-table-based count	`+`
Egg Dropping	`1 + max(left, right)`	`min`
Min/Max expression value	operator-based evaluation	`min` and `max`

Same loop. Same recursive structure. Different tempAns. Different aggregation.

The Solving Flow for Any MCM Problem

When you encounter an MCM problem, go through these six steps in order:

Identify the boundaries. What is i? What is j? What do they represent in this problem?
Find the base case. When i == j, what should you return? When i > j, what should you return?
Define the k range. Usually k goes from i to j-1.
Write the recursive partition. solve(i, k) and solve(k+1, j).
Calculate tempAns. This is the problem-specific step. What does splitting at k cost or produce?
Apply aggregation. min, max, +, or boolean — depending on what the problem is asking for.

The next chapter applies this exact flow to the actual Matrix Chain Multiplication problem, where tempAns is the number of scalar multiplications needed to multiply the matrices from i to j with the split at k.

Quick Revision

Recognition signals:
  Array/string + partition + min/max/count/boolean + multiple split points

Core structure:
  solve(i, j)
    for k in range(i, j):
      left  = solve(i, k)
      right = solve(k+1, j)
      tempAns = combine(left, right)  ← changes per problem
      ans = min/max/count(ans, tempAns)
    return ans

Base cases:
  i == j → smallest valid input (usually return 0)
  i > j  → invalid (return 0)

What's fixed:     i, j boundaries + k loop + left/right recursion
What changes:     tempAns formula + aggregation type

What You Now Understand

MCM is a pattern, not a problem. The structure — range [i, j], partition at every k, recurse on both halves, combine — is the same across all MCM problems. The only creative work is figuring out what tempAns means for the specific problem you're solving.

The next chapter applies this skeleton to Matrix Chain Multiplication specifically: given a chain of matrices, find the minimum number of scalar multiplications needed to compute their product. The tempAns line becomes concrete, and the pattern produces a working solution.

DEV Community: Nishant Gaurav

INSERT, SELECT, UPDATE, DELETE: PostgreSQL

Why this is worth slowing down for

INSERT: getting data in

SELECT: the one you'll use more than everything else combined

UPDATE: changing what's already there

DELETE: same warning, different verb

Where it actually gets interesting: UPSERT

Putting it together: syncing venue data from an external source

Where this leaves you

PostgreSQL Data Types:

A table that works fine until it doesn't

Going through the types one at a time

The table itself

The two questions that always come up

Altering a table isn't always as harmless as it looks

DROP vs TRUNCATE vs DELETE

Fixing a type before it becomes a real migration

Where this leaves you

Getting Into PostgreSQL: psql, Connections, and the First Commands You Actually Need

Why not knowing your way around costs you time

Connecting, and the commands that orient you

Connecting

A few commands worth knowing by heart

Why these are separate from SQL

Where the confusion usually starts: databases, clusters, templates

Creating and dropping a database

What CREATE DATABASE is actually doing

Setting up a project database, step by step

Where this leaves you

Egg Dropping: Min Outside, Max Inside

The Problem

Picking a Floor to Test

Why This Still Looks Like MCM

The Base Cases

The Recursive Solution

A Small Example: E = 2, F = 3

Two Ways to Represent the Same State

Memoization: A 2D Table

The Interval DP Family, Side by Side

Quick Revision

What You Now Understand

Scrambled String: The MCM Skeleton, Now With Two Strings and a Swap Choice

The Problem

Recognising the MCM Pattern

What Happens After You Partition

The Base Cases

The Recursive Solution

Memoizing with a Dictionary

Two Ways to Represent the Same State

The 3D Index-Based Version

Quick Revision

What You Now Understand

Coin Change I: When the Default Value Can Break Everything

The Problem

Why the Initialisation Is Different

Why INF = 2**31 - 2 and Not 2**31 - 1

The DP State

Initialisation in Three Parts

The Transition

The Operation Table

The Complete Code

One Correction Worth Keeping in Your Notes

Quick Revision

What You Now Understand

Boolean Parenthesization: The MCM Skeleton, Counting Instead of Minimising

Boolean Parenthesization: The MCM Skeleton, Counting Instead of Minimising

The Problem

Recognising the MCM Pattern

Why One Number Isn't Enough

The Base Cases

Finding k, Operators Only

The Combining Step

The Recursive Solution

A Small Dry Run

MCM vs Palindrome Partitioning vs Boolean Parenthesization

Quick Revision

What You Now Understand

Palindrome Partitioning: The MCM Skeleton With a New `tempAns`

The Problem

Why `INF = 231 - 2` and Not `231 - 1`

The `tempAns` Line

The Fit Condition: `if i <= j`