import kotlin.math.min

// https://leetcode.com/problems/minimum-path-sum
fun minPathSum(grid: Array<IntArray>): Int {
    val lastRow = grid.lastIndex
    val lastCol = grid.first().lastIndex
    val memo = Array(lastRow + 1) { IntArray(lastCol + 1) }
    memo[lastRow][lastCol] = grid[lastRow][lastCol]
    for (row in lastRow - 1 downTo 0) {
        memo[row][lastCol] = grid[row][lastCol] + memo[row + 1][lastCol]
    }
    for (col in lastCol - 1 downTo 0) {
        memo[lastRow][col] = grid[lastRow][col] + memo[lastRow][col + 1]
    }
    for (row in lastRow - 1 downTo 0) {
        for (col in lastCol - 1 downTo 0) {
            memo[row][col] = grid[row][col] + min(memo[row + 1][col], memo[row][col + 1])
        }
    }
    return memo[0][0]
}
