题目描述
给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
示例 1：
- 输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
- 输出：13
- 解释：
- 所有非零偏移下降路径包括：
- [1,5,9], [1,5,7], [1,6,7], [1,6,8],
- [2,4,8], [2,4,9], [2,6,7], [2,6,8],
- [3,4,8], [3,4,9], [3,5,7], [3,5,9]
- 下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
示例 2：
提示：
n == grid.length == grid[i].length1 <= n <= 200-99 <= grid[i][j] <= 99
解法一：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
func min(nums ...int) int {
res := nums[0]
for _, num := range nums {
if num < res {
res = num
}
}
return res
}
func minFallingPathSum(grid [][]int) int {
n := len(grid)
var dp [2][]int
dp[0], dp[1] = make([]int, n), make([]int, n)
copy(dp[0], grid[0])
for i := 1; i < n; i++ {
for j := 0; j < n; j++ {
dp[1][j] = math.MaxInt32
for k := 0; k < n; k++ {
if k != j {
dp[1][j] = min(dp[1][j], dp[0][k])
}
}
dp[1][j] += grid[i][j]
}
copy(dp[0], dp[1])
}
return min(dp[0]...)
}
|
解法二：转移过程优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
func minFallingPathSum(grid [][]int) int {
n := len(grid)
prevRowPathSum := make([]int, n)
firsMinSum, secondMinSum := 0, 0
for i := 0; i < n; i++ {
t1, t2 := math.MaxInt32, math.MaxInt32
for j := 0; j < n; j++ {
if prevRowPathSum[j] != firsMinSum {
prevRowPathSum[j] = firsMinSum
} else {
prevRowPathSum[j] = secondMinSum
}
prevRowPathSum[j] += grid[i][j]
if prevRowPathSum[j] < t1 {
t2 = t1
t1 = prevRowPathSum[j]
} else if prevRowPathSum[j] < t2 {
t2 = prevRowPathSum[j]
}
}
firsMinSum, secondMinSum = t1, t2
}
return firsMinSum
}
|
