package main

import (
	"fmt"
)

/* func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
} */

func minPathSumOld(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	minGrid := make([][]int, m)
	// 1st col
	for i, sum := 0, 0; i < m; i++ {
		minGrid[i] = make([]int, n)
		sum += grid[i][0]
		minGrid[i][0] = sum
	}
	// 1st row
	for i, sum := 1, grid[0][0]; i < n; i++ {
		sum += grid[0][i]
		minGrid[0][i] = sum
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			minGrid[i][j] = grid[i][j] + minInt(minGrid[i-1][j], minGrid[i][j-1])
		}
	}
	fmt.Println(minGrid)
	return minGrid[m-1][n-1]
}

func minPathSum(grid [][]int) int {
	// no need to create a new minGrid!
	m, n := len(grid), len(grid[0])
	// 1st col
	for i := 1; i < m; i++ {
		grid[i][0] += grid[i-1][0]
	}
	// 1st row
	for i := 1; i < n; i++ {
		grid[0][i] += grid[0][i-1]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			grid[i][j] += minInt(grid[i-1][j], grid[i][j-1])
		}
	}
	return grid[m-1][n-1]
}

/* func main() {
	g1 := [][]int{
		{1, 3, 1},
		{1, 5, 1},
		{4, 2, 1},
	}
	fmt.Println(minPathSum(g1))
} */