notes.html

problem 81 · 21 lines

<article>
<h3>Problem Analysis</h3>
<p>
This problem asks for the minimum-cost path through a square grid, starting at the top-left cell and ending at the bottom-right, where the only legal moves are one step right or one step down. The structural observation that makes this tractable is that the movement restriction sharply limits how a path can arrive at any cell: a cell at position (r, c) can only be reached from the cell directly above it, (r-1, c), or the one directly to its left, (r, c-1). Consequently, the cheapest route through (r, c) depends only on the cheapest routes to its two neighbours plus its own value. This property - that the best solution to the whole problem can be assembled from the best solutions to smaller, overlapping sub-problems - is called <a class="reference-source" href="https://en.wikipedia.org/wiki/Optimal_substructure" rel="noopener noreferrer" target="_blank">optimal substructure</a>, and it is the hallmark of a problem amenable to <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> (DP), a technique that solves a problem by caching and reusing answers to sub-problems instead of re-deriving them.
</p>
<p>
A brute-force enumeration of every right/down path is hopeless: the number of monotone paths across an N x N grid grows like a central <a class="reference-source" href="https://en.wikipedia.org/wiki/Binomial_coefficient" rel="noopener noreferrer" target="_blank">binomial coefficient</a>, which is exponential in N. <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">Dynamic programming</a> collapses this entirely. Let <code>cost[r][c]</code> be the minimum cost to travel from (r, c) to the bottom-right corner. Then <code>cost[r][c] = matrix[r][c] + min(cost[r+1][c], cost[r][c+1])</code>, with the bottom-right corner as the base case - it has no successors, so its cost is just its own value. Each of the N x N cells is computed once with constant work, so the algorithm runs in O(N^2) time and, by overwriting the matrix in place, O(1) extra space. For the 80 x 80 grid that is only 6400 cells - trivially fast. It also helps to see the grid as a <a class="reference-source" href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noopener noreferrer" target="_blank">directed acyclic graph</a> (DAG), where each cell is a node and each legal move is a directed edge; shortest-path DP on a DAG is always linear in nodes plus edges.
</p>
<h3>Solution Approach</h3>
<h4>Diagonal Backward-Fill (Python and C)</h4>
<p>
Both the Python and C solutions implement the same algorithm, which I call "diagonal backward-fill". Rather than allocating a separate DP table, I overwrite each cell of the matrix with the minimum cost to reach the bottom-right corner from that cell. I process cells in reverse, walking from the bottom-right corner toward the top-left in <a class="reference-source" href="https://en.wikipedia.org/wiki/Diagonal" rel="noopener noreferrer" target="_blank">anti-diagonal</a> bands. An anti-diagonal is the set of cells where (r + c) is constant; all such cells are the same number of steps from the corner, so they are mutually independent and can be visited in any order within a band.
</p>
<p>
The traversal order is dictated by the recurrence. When I compute <code>cost[r][c]</code>, I need its right neighbour (r, c+1) and its lower neighbour (r+1, c) to already hold their final values. Both of those lie on an anti-diagonal closer to the bottom-right corner, so visiting diagonals in reverse guarantees the dependency is satisfied. This is precisely a <a class="reference-source" href="https://en.wikipedia.org/wiki/Topological_sorting" rel="noopener noreferrer" target="_blank">topological sort</a> of the cell-dependency <a class="reference-source" href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noopener noreferrer" target="_blank">DAG</a>, but it exploits the regular grid layout so no explicit graph is ever built. I chose this reverse-diagonal sweep specifically because it lets me reuse the input matrix as the DP table: every cell is read and finalised before any cell that depends on it is overwritten.
</p>
<p>
For each cell I collect whichever of the two successor neighbours exist (the bottom-right corner has neither, the last row has only a right neighbour, the last column only a lower one), add the smaller of them to the cell's own value, and write the result back. When the walk finishes, <code>matrix[0][0]</code> holds the answer. In Python the traversal order is produced by the <a class="reference-source" href="https://wiki.python.org/moin/Generators" rel="noopener noreferrer" target="_blank">generator</a> <code>move_diagonally</code>, which yields one (row, col) pair at a time; the C version pre-computes the identical sequence into two parallel arrays <code>rows</code> and <code>cols</code> via <code>move_diagonally_all</code>, then iterates over them. The logic is identical - the difference is Python's lazy <a class="reference-source" href="https://wiki.python.org/moin/Generators" rel="noopener noreferrer" target="_blank">generator</a> versus C's eager arrays. The neighbour bookkeeping differs only slightly: Python builds a small list and uses <code>min(neighbors, default=0)</code> to handle the empty case, while C tracks a running minimum initialised to -1 as a sentinel meaning "no neighbour yet".
</p>
</article>