package main

import (
	"fmt"
	"math"
)

func minCostII(costs [][]int) int {
	n, k := len(costs), len(costs[0])
	dp := make([][]int,n + 1, n + 1)
	for i := 0 ; i < n + 1 ; i ++{
		dp[i] = make([]int,k,k)
	}
	// 1.初始化dp
	for i := 0 ; i < k ; i ++ {
		dp[0][i] = costs[0][i]
	}
	// 2.填充dp
	for i := 1 ; i < n ; i++ {
		for j := 0 ; j < k ; j ++ {
			minDP := math.MaxInt32
			for m := 0 ; m < k ; m ++ {
				if m == j {
					continue
				}
				if minDP > dp[i-1][m] {
					 minDP = dp[i-1][m]
				}
			}
			dp[i][j] = minDP + costs[i][j]
		}
	}
	res := math.MaxInt32
	for i := 0 ; i < k ; i++ {
		if dp[n-1][i] < res {
			res = dp[n-1][i]
		}
	}
	return res
}

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

func main() {
	arr := [][]int{{3,20,7,7,16,8,7,12,11,19,1},{10,14,3,3,9,13,4,12,14,13,1}}
	fmt.Println(minCostII(arr))
}