Grid and Coordinate DP

Opening scenario

Problem references use LC for LeetCode.

Given an m × n grid of non-negative numbers, find a path from top-left to bottom-right that minimizes the sum along the path. You can only move right or down (LC 64, Minimum Path Sum). The interviewer will then twist the same grid in one of these ways:

• Count the right-and-down routes instead of minimizing.
• Block some cells and count only the routes that avoid them.
• Drain or restore health in each room. Return the smallest starting health that keeps you at 1 or above.
• Drop the right-and-down rule and allow all four directions. Count the routes that step on every open cell exactly once.

Assume non-empty rectangular grids, with m ≥ 1 rows and n ≥ 1 columns. Minimum Path Sum includes both endpoint values. Begin by listing the cells from which a legal move can enter a given position.

Question progression

Q1 — Why is the cell coordinate itself the state?

Question: For LC 64…