题目描述：
给出一个 $n\times n$ 整数矩阵grid，请返回非零偏移下降路径数字和的最小值。
非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
数据范围：
$1\le n \le 200, -99 \le grid[i][j] \le 99$
题解：
使用动态规划，每次从上一行转移到下一行。对于 $dp[i][j]$ 来说，需要找 $dp[i-1][k],k\ne j$ 。
这样的话需要使用三重循环，时间复杂度比较高。
可以发现 $dp[i][j]$ 依赖于 $dp[i-1][k]$ ，并且重复了很多。可以只记录上一行中的最小值和次最小值。如果当前的下标和上一行最小值的下标相同，就选择上一行的次最小值，否则选择上一行中的最小值。
代码：
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
30
31
32
33
34
35
36
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minFallingPathSum(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dp(n, vector<int>(m, INF));
for (int j = 0; j < m; ++j)
dp[0][j] = grid[0][j];
for (int i = 1; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
for (int k = 0; k < m; ++k)
{
if(k == j) continue;
dp[i][j] = min(dp[i - 1][k] + grid[i][j], dp[i][j]);
}
}
}
int ans = INF;
for (int j = 0; j < m; ++j)
ans = min(ans, dp[n - 1][j]);
return ans;
}
};
|
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
30
31
32
33
34
35
36
37
38
39
40
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int minFallingPathSum(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
int last_first_minx = 0, last_second_minx = 0, last_minx_index = -1;
int dpij;
for (int i = 0; i < n; ++i)
{
int cur_first_minx = INF, cur_second_minx = INF, cur_minx_index = -1;
for (int j = 0; j < m; ++j)
{
dpij = (j == last_minx_index ? last_second_minx : last_first_minx) + grid[i][j];
if (dpij < cur_first_minx)
{
cur_second_minx = cur_first_minx;
cur_first_minx = dpij;
cur_minx_index = j;
}
else if (dpij < cur_second_minx)
cur_second_minx = dpij;
}
last_first_minx = cur_first_minx;
last_second_minx = cur_second_minx;
last_minx_index = cur_minx_index;
}
return last_first_minx;
}
};
|