题解 | #矩阵的最小路径和#

package main

import (
    "bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func minSumPathDp(tables [][]int) int {
	dp := make([][]int, len(tables))
	for row := 0; row < len(tables); row++ {
		dp[row] = make([]int, len(tables[0]))
	}
	dp[0][0] = tables[0][0]
	for row := 1; row < len(tables); row++ {
		dp[row][0] = tables[row][0] + dp[row-1][0]
	}
	for col := 1; col < len(tables[0]); col++ {
		dp[0][col] = tables[0][col] + dp[0][col-1]
	}
	//开始dp
	for row := 1; row < len(tables); row++ {
		for col := 1; col < len(tables[0]); col++ {
			dp[row][col] = min(tables[row][col]+dp[row][col-1], tables[row][col]+dp[row-1][col])
		}
	}
	return dp[len(dp)-1][len(dp[0])-1]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

/*
*
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
结果12
*/
func main() {
	// tables := make([][]int, 4)
	// tables[0] = []int{1, 3, 5, 9}
	// tables[1] = []int{8, 1, 3, 4}
	// tables[2] = []int{5, 0, 6, 1}
	// tables[3] = []int{8, 8, 4, 0}
	// fmt.Println(solution(tables))

	var row, col int
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	str := scanner.Text()
	strs := strings.Split(str, " ")
	row, _ = strconv.Atoi(strs[0])
	col, _ = strconv.Atoi(strs[1])
	tables := make([][]int, 0)
	for i := 0; i < row; i++ {
		scanner.Scan()
		str = scanner.Text()
		strs = strings.Split(str, " ")
		tmp := make([]int, col)
		for j := 0; j < len(strs); j++ {
			ele, _ := strconv.Atoi(strs[j])
			tmp[j] = ele
		}
		tables = append(tables, tmp)
	}
	
	fmt.Println(minSumPathDp(tables))
}