問題の概要

左上のセル (0, 0) から右下のセル (m-1, n-1) まで、右または下のみ移動して到達する経路のうち、通過したセルの値の合計が最小となるものを求めます。

DP の定式化

dp[i][j] を「(i, j) まで到達する経路の最小値」とします。到達できる移元は上方向か左方向のみなので、次の漸化式が成り立ちます。

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

初期条件は、最初の行・列は一直線にしか進めないため累積和で埋めます。

実装例 1：メモ化再帰

トップダウンで同じ計算を防ぎます。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int h = grid.size();
        int w = grid[0].size();
        memo.assign(h, vector<int>(w, -1));
        this->g = &grid;
        return dfs(0, 0, h, w);
    }

private:
    vector<vector<int>> memo;
    vector<vector<int>>* g;
    static constexpr int INF = 1e9;

    int dfs(int y, int x, int h, int w) {
        if (y >= h || x >= w) return INF;
        int& res = memo[y][x];
        if (res != -1) return res;
        if (y == h - 1 && x == w - 1) return res = (*g)[y][x];

        int down = dfs(y + 1, x, h, w);
        int right = dfs(y, x + 1, h, w);
        return res = min(down, right) + (*g)[y][x];
    }
};

実装例 2：2 次元 DP

初期行・列を先に確定させ、残りを反復的に埋めます。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();

        vector<vector<int>> cost(rows, vector<int>(cols, 0));
        cost[0][0] = grid[0][0];

        for (int c = 1; c < cols; ++c) {
            cost[0][c] = cost[0][c - 1] + grid[0][c];
        }
        for (int r = 1; r < rows; ++r) {
            cost[r][0] = cost[r - 1][0] + grid[r][0];
        }

        for (int r = 1; r < rows; ++r) {
            for (int c = 1; c < cols; ++c) {
                cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c];
            }
        }

        return cost[rows - 1][cols - 1];
    }
};

実装例 3：1 次元 DP（空間圧縮)

各行の更新は左隣の値と前回の値だけで足りるため、配列を 1 本に削減できます。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();

        vector<int> cur(cols, 0);
        cur[0] = grid[0][0];
        for (int c = 1; c < cols; ++c) {
            cur[c] = cur[c - 1] + grid[0][c];
        }

        for (int r = 1; r < rows; ++r) {
            cur[0] += grid[r][0];
            for (int c = 1; c < cols; ++c) {
                cur[c] = min(cur[c - 1], cur[c]) + grid[r][c];
            }
        }

        return cur[cols - 1];
    }
};

計算量

• 時間計算量：O(m × n)
• 空間計算量：
  • メモ化再帰・2 次元 DP：O(m × n)
  • 1 次元 DP：O(n)