Problem Analysis
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 optimal substructure, and it is the hallmark of a problem amenable to dynamic programming (DP), a technique that solves a problem by caching and reusing answers to sub-problems instead of re-deriving them.
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 binomial coefficient, which is exponential in N. Dynamic programming collapses this entirely. Let cost[r][c] be the minimum cost to travel from (r, c) to the bottom-right corner. Then cost[r][c] = matrix[r][c] + min(cost[r+1][c], cost[r][c+1]), 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 directed acyclic graph (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.
Solution Approach
Diagonal Backward-Fill (Python and C)
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 anti-diagonal 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.
The traversal order is dictated by the recurrence. When I compute cost[r][c], 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 topological sort of the cell-dependency DAG, 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.
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, matrix[0][0] holds the answer. In Python the traversal order is produced by the generator move_diagonally, which yields one (row, col) pair at a time; the C version pre-computes the identical sequence into two parallel arrays rows and cols via move_diagonally_all, then iterates over them. The logic is identical - the difference is Python's lazy generator versus C's eager arrays. The neighbour bookkeeping differs only slightly: Python builds a small list and uses min(neighbors, default=0) to handle the empty case, while C tracks a running minimum initialised to -1 as a sentinel meaning "no neighbour yet".