Grid paths

def min_path_sum(grid):
    """Cheapest path from the top-left to the bottom-right cell, moving only
    right or down. Returns (cost, moves), moves as a string of 'R' and 'D'."""
    rows, cols = len(grid), len(grid[0])
    INF = float("inf")
    # dp[r][c] = cheapest cost of reaching cell (r, c), both ends included
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                dp[0][0] = grid[0][0]
                continue
            up = dp[r - 1][c] if r > 0 else INF
            left = dp[r][c - 1] if c > 0 else INF
            dp[r][c] = grid[r][c] + min(up, left)

    # Walk back from the corner to the neighbour each cell was built from.
    moves = []
    r, c = rows - 1, cols - 1
    while r > 0 or c > 0:
        if c == 0 or (r > 0 and dp[r - 1][c] <= dp[r][c - 1]):
            moves.append("D")
            r -= 1
        else:
            moves.append("R")
            c -= 1
    return dp[rows - 1][cols - 1], "".join(reversed(moves))

#include <algorithm>
#include <climits>
#include <string>
#include <utility>
#include <vector>
using namespace std;

// Cheapest path from the top-left to the bottom-right cell, moving only right
// or down. Returns {cost, moves}, moves as a string of 'R' and 'D'.
pair<long long, string> minPathSum(const vector<vector<long long>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    const long long INF = LLONG_MAX;
    // dp[r][c] = cheapest cost of reaching cell (r, c), both ends included
    vector<vector<long long>> dp(rows, vector<long long>(cols, 0));
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (r == 0 && c == 0) {
                dp[0][0] = grid[0][0];
                continue;
            }
            long long up = r > 0 ? dp[r - 1][c] : INF;
            long long left = c > 0 ? dp[r][c - 1] : INF;
            dp[r][c] = grid[r][c] + min(up, left);
        }
    }

    // Walk back from the corner to the neighbour each cell was built from.
    string moves;
    int r = rows - 1, c = cols - 1;
    while (r > 0 || c > 0) {
        if (c == 0 || (r > 0 && dp[r - 1][c] <= dp[r][c - 1])) {
            moves += 'D';
            r--;
        } else {
            moves += 'R';
            c--;
        }
    }
    reverse(moves.begin(), moves.end());
    return {dp[rows - 1][cols - 1], moves};
}

class GridPaths {
    // Cheapest path from the top-left to the bottom-right cell, moving only
    // right or down. Returns the cost; the moves ('R' and 'D') go into `moves`.
    static long minPathSum(long[][] grid, StringBuilder moves) {
        int rows = grid.length, cols = grid[0].length;
        final long INF = Long.MAX_VALUE;
        // dp[r][c] = cheapest cost of reaching cell (r, c), both ends included
        long[][] dp = new long[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == 0 && c == 0) {
                    dp[0][0] = grid[0][0];
                    continue;
                }
                long up = r > 0 ? dp[r - 1][c] : INF;
                long left = c > 0 ? dp[r][c - 1] : INF;
                dp[r][c] = grid[r][c] + Math.min(up, left);
            }
        }

        // Walk back from the corner to the neighbour each cell was built from.
        int r = rows - 1, c = cols - 1;
        while (r > 0 || c > 0) {
            if (c == 0 || (r > 0 && dp[r - 1][c] <= dp[r][c - 1])) {
                moves.append('D');
                r--;
            } else {
                moves.append('R');
                c--;
            }
        }
        moves.reverse();
        return dp[rows - 1][cols - 1];
    }
}