Return to Question

Output: 7

Explanation: Because the path \$ 1 \to 3 \to 1 \to 1 \to 1 \$ minimizes the sum.

Output: 7

Explanation: Because the path \$ 1 \to 3 \to 1 \to 1 \to 1 \$ minimizes the sum.

import pandas as pd


class PathFinder:
    """
    Path maximizer / minimizer
    """

    def __init__(self, matrix, start_point=(0, 0)):
        """
        Initialize finder settings.
        Args:
            matrix: 2D list
            start_point: x, y coordinates to start from.
        """
        x1, y1 = start_point
        self.matrix = matrix[x1:][y1:]
        self.seen = {}
        self.x_size = len(self.matrix)
        self.y_size = len(self.matrix[0])
        self.end_x = self.x_size - 1
        self.end_y = self.y_size - 1
        self.initial_frame, self.processed_frame = (None, None)

    def _get_possible_moves(self, x, y):
        """
        Get possible next moves.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            possible_moves.
        """
        possible_moves = []
        if x < self.end_x:
            possible_moves.append([x + 1, y])
        if y < self.end_y:
            possible_moves.append([x, y + 1])
        return possible_moves

    def get_path_sum(self, x, y, mode='min'):
        """
        Get minimum / maximum path sum following right and down steps only.
        Args:
            x: x coordinate.
            y: y coordinate.
            mode: 'min' or 'max'

        Returns:
            Minimum or Maximum path sum.
        """
        assert mode in ('min', 'max'), f'Invalid mode {mode}'
        if (x, y) in self.seen:
            return self.seen[x, y]
        current = self.matrix[x][y]
        if x == self.end_x and y == self.end_y:
            return current
        possible_moves = self._get_possible_moves(x, y)
        results = [
            current + self.get_path_sum(*possible, mode) for possible in possible_moves
        ]
        current_best = min(results) if mode == 'min' else max(results)
        self.seen[x, y] = current_best
        return current_best

    def _create_frames(self):
        """
        Create pandas DataFrame to preview path followed.

        Returns:
            Initial frame and a copy.
        """
        pd.set_option('expand_frame_repr', False)
        initial_frame = pd.DataFrame(self.matrix)
        return initial_frame, initial_frame.copy()

    def _modify_coordinate(self, x, y):
        """
        Mark a coordinate that is in the min/mx path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            None
        """
        n = self.processed_frame.loc[x, y]
        self.processed_frame.loc[x, y] = f'({n})'

    def _update_xy(self, x, y):
        """
        Follow and mark 1 step of the path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            x, y update.
        """
        current_n = self.matrix[x][y]
        current_best = self.seen[x, y]
        right_best = self.seen[x, y + 1]
        down_best = self.seen[x + 1, y]
        if current_best - right_best == current_n:
            self._modify_coordinate(x, y + 1)
            return x, y + 1
        if current_best - down_best == current_n:
            self._modify_coordinate(x + 1, y)
            return x + 1, y

    def draw_path(self):
        """
        Draw path followed using seen values.

        Returns:
            2 pandas DataFrames one containing path and another empty.
        """
        self.initial_frame, self.processed_frame = self._create_frames()
        x, y = 0, 0
        self._modify_coordinate(x, y)
        while x <= self.end_x or y <= self.end_y:
            if y == self.end_y:
                for i in range(x + 1, self.x_size):
                    self._modify_coordinate(i, y)
                break
            if x == self.end_x:
                for i in range(y + 1, self.y_size):
                    self._modify_coordinate(x, i)
                break
            x, y = self._update_xy(x, y)
        return self.initial_frame, self.processed_frame


if __name__ == '__main__':
    m = [
        [7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5],
        [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6],
        [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8],
        [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4],
        [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4],
        [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9],
        [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4],
        [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2],
        [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3],
        [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7],
        [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7],
        [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9],
    ]
    finder = PathFinder(m)
    print(finder.get_path_sum(0, 0))
    print(finder.draw_path()[1])

import pandas as pd


class PathFinder:
    """
    Path maximizer / minimizer
    """

    def __init__(self, matrix, start_point=(0, 0)):
        """
        Initialize finder settings.
        Args:
            matrix: 2D list
            start_point: x, y coordinates to start from.
        """
        x1, y1 = start_point
        self.matrix = matrix[x1:][y1:]
        self.seen = {}
        self.x_size = len(self.matrix)
        self.y_size = len(self.matrix[0])
        self.end_x = self.x_size - 1
        self.end_y = self.y_size - 1
        self.initial_frame, self.processed_frame = (None, None)

    def _get_possible_moves(self, x, y):
        """
        Get possible next moves.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            possible_moves.
        """
        possible_moves = []
        if x < self.end_x:
            possible_moves.append([x + 1, y])
        if y < self.end_y:
            possible_moves.append([x, y + 1])
        return possible_moves

    def get_path_sum(self, x, y, mode='min'):
        """
        Get minimum / maximum path sum following right and down steps only.
        Args:
            x: x coordinate.
            y: y coordinate.
            mode: 'min' or 'max'

        Returns:
            Minimum or Maximum path sum.
        """
        assert mode in ('min', 'max'), f'Invalid mode {mode}'
        if (x, y) in self.seen:
            return self.seen[x, y]
        current = self.matrix[x][y]
        if x == self.end_x and y == self.end_y:
            return current
        possible_moves = self._get_possible_moves(x, y)
        results = [
            current + self.get_path_sum(*possible, mode) for possible in possible_moves
        ]
        current_best = min(results) if mode == 'min' else max(results)
        self.seen[x, y] = current_best
        return current_best

    def _create_frames(self):
        """
        Create pandas DataFrame to preview path followed.

        Returns:
            Initial frame and a copy.
        """
        pd.set_option('expand_frame_repr', False)
        initial_frame = pd.DataFrame(self.matrix)
        return initial_frame, initial_frame.copy()

    def _modify_coordinate(self, x, y):
        """
        Mark a coordinate that is in the min/max path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            None
        """
        n = self.processed_frame.loc[x, y]
        self.processed_frame.loc[x, y] = f'({n})'

    def _update_xy(self, x, y):
        """
        Follow and mark 1 step of the path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            x, y update.
        """
        current_n = self.matrix[x][y]
        current_best = self.seen[x, y]
        right_best = self.seen[x, y + 1]
        down_best = self.seen[x + 1, y]
        if current_best - right_best == current_n:
            self._modify_coordinate(x, y + 1)
            return x, y + 1
        if current_best - down_best == current_n:
            self._modify_coordinate(x + 1, y)
            return x + 1, y

    def draw_path(self):
        """
        Draw path followed using seen values.

        Returns:
            2 pandas DataFrames one containing path and another empty.
        """
        self.initial_frame, self.processed_frame = self._create_frames()
        x, y = 0, 0
        self._modify_coordinate(x, y)
        while x <= self.end_x or y <= self.end_y:
            if y == self.end_y:
                for i in range(x + 1, self.x_size):
                    self._modify_coordinate(i, y)
                break
            if x == self.end_x:
                for i in range(y + 1, self.y_size):
                    self._modify_coordinate(x, i)
                break
            x, y = self._update_xy(x, y)
        return self.initial_frame, self.processed_frame


if __name__ == '__main__':
    m = [
        [7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5],
        [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6],
        [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8],
        [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4],
        [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4],
        [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9],
        [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4],
        [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2],
        [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3],
        [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7],
        [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7],
        [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9],
    ]
    finder = PathFinder(m)
    print(finder.get_path_sum(0, 0))
    print(finder.draw_path()[1])

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

path_sum.py

import pandas as pd


class PathFinder:
    """
    Path maximizer / minimizer
    """

    def __init__(self, matrix, start_point=(0, 0)):
        """
        Initialize finder settings.
        Args:
            matrix: 2D list
            start_point: x, y coordinates to start from.
        """
        x1, y1 = start_point
        self.matrix = matrix[x1:][y1:]
        self.seen = {}
        self.x_size = len(self.matrix)
        self.y_size = len(self.matrix[0])
        self.end_x = self.x_size - 1
        self.end_y = self.y_size - 1
        self.initial_frame, self.processed_frame = (None, None)

    def _get_possible_moves(self, x, y):
        """
        Get possible next moves.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            possible_moves.
        """
        possible_moves = []
        if x < self.end_x:
            possible_moves.append([x + 1, y])
        if y < self.end_y:
            possible_moves.append([x, y + 1])
        return possible_moves

    def get_path_sum(self, x, y, mode='min'):
        """
        Get minimum / maximum path sum following right and down steps only.
        Args:
            x: x coordinate.
            y: y coordinate.
            mode: 'min' or 'max'

        Returns:
            Minimum or Maximum path sum.
        """
        assert mode in ('min', 'max'), f'Invalid mode {mode}'
        if (x, y) in self.seen:
            return self.seen[x, y]
        current = self.matrix[x][y]
        if x == self.end_x and y == self.end_y:
            return current
        possible_moves = self._get_possible_moves(x, y)
        results = [
            current + self.get_path_sum(*possible, mode) for possible in possible_moves
        ]
        current_best = min(results) if mode == 'min' else max(results)
        self.seen[x, y] = current_best
        return current_best

    def _create_frames(self):
        """
        Create pandas DataFrame to preview path followed.

        Returns:
            Initial frame and a copy.
        """
        pd.set_option('expand_frame_repr', False)
        initial_frame = pd.DataFrame(self.matrix)
        return initial_frame, initial_frame.copy()

    def _modify_coordinate(self, x, y):
        """
        Mark a coordinate that is in the min/mx path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            None
        """
        n = self.processed_frame.loc[x, y]
        self.processed_frame.loc[x, y] = f'({n})'

    def _update_xy(self, x, y):
        """
        Follow and mark 1 step of the path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            x, y update.
        """
        current_n = self.matrix[x][y]
        current_best = self.seen[x, y]
        right_best = self.seen[x, y + 1]
        down_best = self.seen[x + 1, y]
        if current_best - right_best == current_n:
            self._modify_coordinate(x, y + 1)
            return x, y + 1
        if current_best - down_best == current_n:
            self._modify_coordinate(x + 1, y)
            return x + 1, y

    def draw_path(self):
        """
        Draw path followed using seen values.

        Returns:
            2 pandas DataFrames one containing path and another empty.
        """
        self.initial_frame, self.processed_frame = self._create_frames()
        x, y = 0, 0
        self._modify_coordinate(x, y)
        while x <= self.end_x or y <= self.end_y:
            if y == self.end_y:
                for i in range(x + 1, self.x_size):
                    self._modify_coordinate(i, y)
                break
            if x == self.end_x:
                for i in range(y + 1, self.y_size):
                    self._modify_coordinate(x, i)
                break
            x, y = self._update_xy(x, y)
        return self.initial_frame, self.processed_frame


if __name__ == '__main__':
    m = [
        [7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5],
        [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6],
        [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8],
        [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4],
        [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4],
        [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9],
        [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4],
        [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2],
        [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3],
        [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7],
        [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7],
        [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9],
    ]
    finder = PathFinder(m)
    print(finder.get_path_sum(0, 0))
    print(finder.draw_path()[1])

path_sum.h

#ifndef LEETCODE_PATH_SUM_H
#define LEETCODE_PATH_SUM_H

#include <vector>
#include <string>

int path_sum(const std::vector<std::vector<int>> &matrix, int x, int y,
             std::vector<std::vector<int>> &seen, int empty_value = -1,
             const std::string& mode = "min");

#endif //LEETCODE_PATH_SUM_H

path_sum.cpp

#include "path_sum.h"
#include <algorithm>
#include <iostream>


int path_sum(const std::vector<std::vector<int>> &matrix, int x, int y,
             std::vector<std::vector<int>> &seen, int empty_value,
             const std::string &mode) {
    int seen_value{seen[x][y]};
    if (seen_value != empty_value)
        return seen_value;
    auto x_end = matrix.size() - 1;
    auto y_end = matrix[0].size() - 1;
    int current = matrix[x][y];
    if (x == x_end && y == y_end)
        return current;
    std::vector<int> results;
    if (x < x_end)
        results.push_back(
            current + path_sum(matrix, x + 1, y, seen, empty_value, mode));
    if (y < y_end)
        results.push_back(
            current + path_sum(matrix, x, y + 1, seen, empty_value, mode));
    int current_best;
    switch (results.size()) {
    case 1:
        seen[x][y] = results[0];
        return results[0];
    case 2:
        int n1{results[0]};
        int n2{results[1]};
        current_best = (mode == "min") ? std::min(n1, n2) : std::max(n1, n2);
    }
    seen[x][y] = current_best;
    return current_best;
}


int main() {
    std::vector<std::vector<int>> matrix{
        {7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5},
        {9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6},
        {8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8},
        {6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4},
        {7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4},
        {9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9},
        {1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4},
        {3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2},
        {1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3},
        {5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7},
        {2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7},
        {0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9}
    };
    std::vector<std::vector<int>> seen(matrix.size(),
                                       std::vector<int>(matrix[0].size(), -1));
    std::cout << "Minimum: " << path_sum(matrix, 0, 0, seen);
}

Given a \$ m \times n \$ grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Explanation: Because the path \$ 1 \to 3 \to 1 \to 1 \to 1 \$ minimizes the sum.

path_sum.py

import pandas as pd


class PathFinder:
    """
    Path maximizer / minimizer
    """

    def __init__(self, matrix, start_point=(0, 0)):
        """
        Initialize finder settings.
        Args:
            matrix: 2D list
            start_point: x, y coordinates to start from.
        """
        x1, y1 = start_point
        self.matrix = matrix[x1:][y1:]
        self.seen = {}
        self.x_size = len(self.matrix)
        self.y_size = len(self.matrix[0])
        self.end_x = self.x_size - 1
        self.end_y = self.y_size - 1
        self.initial_frame, self.processed_frame = (None, None)

    def _get_possible_moves(self, x, y):
        """
        Get possible next moves.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            possible_moves.
        """
        possible_moves = []
        if x < self.end_x:
            possible_moves.append([x + 1, y])
        if y < self.end_y:
            possible_moves.append([x, y + 1])
        return possible_moves

    def get_path_sum(self, x, y, mode='min'):
        """
        Get minimum / maximum path sum following right and down steps only.
        Args:
            x: x coordinate.
            y: y coordinate.
            mode: 'min' or 'max'

        Returns:
            Minimum or Maximum path sum.
        """
        assert mode in ('min', 'max'), f'Invalid mode {mode}'
        if (x, y) in self.seen:
            return self.seen[x, y]
        current = self.matrix[x][y]
        if x == self.end_x and y == self.end_y:
            return current
        possible_moves = self._get_possible_moves(x, y)
        results = [
            current + self.get_path_sum(*possible, mode) for possible in possible_moves
        ]
        current_best = min(results) if mode == 'min' else max(results)
        self.seen[x, y] = current_best
        return current_best

    def _create_frames(self):
        """
        Create pandas DataFrame to preview path followed.

        Returns:
            Initial frame and a copy.
        """
        pd.set_option('expand_frame_repr', False)
        initial_frame = pd.DataFrame(self.matrix)
        return initial_frame, initial_frame.copy()

    def _modify_coordinate(self, x, y):
        """
        Mark a coordinate that is in the min/mx path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            None
        """
        n = self.processed_frame.loc[x, y]
        self.processed_frame.loc[x, y] = f'({n})'

    def _update_xy(self, x, y):
        """
        Follow and mark 1 step of the path.
        Args:
            x: x coordinate.
            y: y coordinate.

        Returns:
            x, y update.
        """
        current_n = self.matrix[x][y]
        current_best = self.seen[x, y]
        right_best = self.seen[x, y + 1]
        down_best = self.seen[x + 1, y]
        if current_best - right_best == current_n:
            self._modify_coordinate(x, y + 1)
            return x, y + 1
        if current_best - down_best == current_n:
            self._modify_coordinate(x + 1, y)
            return x + 1, y

    def draw_path(self):
        """
        Draw path followed using seen values.

        Returns:
            2 pandas DataFrames one containing path and another empty.
        """
        self.initial_frame, self.processed_frame = self._create_frames()
        x, y = 0, 0
        self._modify_coordinate(x, y)
        while x <= self.end_x or y <= self.end_y:
            if y == self.end_y:
                for i in range(x + 1, self.x_size):
                    self._modify_coordinate(i, y)
                break
            if x == self.end_x:
                for i in range(y + 1, self.y_size):
                    self._modify_coordinate(x, i)
                break
            x, y = self._update_xy(x, y)
        return self.initial_frame, self.processed_frame


if __name__ == '__main__':
    m = [
        [7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5],
        [9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6],
        [8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8],
        [6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4],
        [7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4],
        [9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9],
        [1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4],
        [3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2],
        [1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3],
        [5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7],
        [2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7],
        [0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9],
    ]
    finder = PathFinder(m)
    print(finder.get_path_sum(0, 0))
    print(finder.draw_path()[1])

path_sum.h

#ifndef LEETCODE_PATH_SUM_H
#define LEETCODE_PATH_SUM_H

#include <vector>
#include <string>

int path_sum(const std::vector<std::vector<int>> &matrix, int x, int y,
             std::vector<std::vector<int>> &seen, int empty_value = -1,
             const std::string& mode = "min");

#endif //LEETCODE_PATH_SUM_H

path_sum.cpp

#include "path_sum.h"
#include <algorithm>
#include <iostream>


int path_sum(const std::vector<std::vector<int>> &matrix, int x, int y,
             std::vector<std::vector<int>> &seen, int empty_value,
             const std::string &mode) {
    int seen_value{seen[x][y]};
    if (seen_value != empty_value)
        return seen_value;
    auto x_end = matrix.size() - 1;
    auto y_end = matrix[0].size() - 1;
    int current = matrix[x][y];
    if (x == x_end && y == y_end)
        return current;
    std::vector<int> results;
    if (x < x_end)
        results.push_back(
            current + path_sum(matrix, x + 1, y, seen, empty_value, mode));
    if (y < y_end)
        results.push_back(
            current + path_sum(matrix, x, y + 1, seen, empty_value, mode));
    int current_best;
    switch (results.size()) {
    case 1:
        seen[x][y] = results[0];
        return results[0];
    case 2:
        int n1{results[0]};
        int n2{results[1]};
        current_best = (mode == "min") ? std::min(n1, n2) : std::max(n1, n2);
    }
    seen[x][y] = current_best;
    return current_best;
}


int main() {
    std::vector<std::vector<int>> matrix{
        {7, 1, 3, 5, 8, 9, 9, 2, 1, 9, 0, 8, 3, 1, 6, 6, 9, 5},
        {9, 5, 9, 4, 0, 4, 8, 8, 9, 5, 7, 3, 6, 6, 6, 9, 1, 6},
        {8, 2, 9, 1, 3, 1, 9, 7, 2, 5, 3, 1, 2, 4, 8, 2, 8, 8},
        {6, 7, 9, 8, 4, 8, 3, 0, 4, 0, 9, 6, 6, 0, 0, 5, 1, 4},
        {7, 1, 3, 1, 8, 8, 3, 1, 2, 1, 5, 0, 2, 1, 9, 1, 1, 4},
        {9, 5, 4, 3, 5, 6, 1, 3, 6, 4, 9, 7, 0, 8, 0, 3, 9, 9},
        {1, 4, 2, 5, 8, 7, 7, 0, 0, 7, 1, 2, 1, 2, 7, 7, 7, 4},
        {3, 9, 7, 9, 5, 8, 9, 5, 6, 9, 8, 8, 0, 1, 4, 2, 8, 2},
        {1, 5, 2, 2, 2, 5, 6, 3, 9, 3, 1, 7, 9, 6, 8, 6, 8, 3},
        {5, 7, 8, 3, 8, 8, 3, 9, 9, 8, 1, 9, 2, 5, 4, 7, 7, 7},
        {2, 3, 2, 4, 8, 5, 1, 7, 2, 9, 5, 2, 4, 2, 9, 2, 8, 7},
        {0, 1, 6, 1, 1, 0, 0, 6, 5, 4, 3, 4, 3, 7, 9, 6, 1, 9}
    };
    std::vector<std::vector<int>> seen(matrix.size(),
                                       std::vector<int>(matrix[0].size(), -1));
    std::cout << "Minimum: " << path_sum(matrix, 0, 0, seen);
}