矩阵的最小路径和
题目描述：
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
输入描述：
第一行输入两个整数 n 和 m，表示矩阵的大小。
接下来 n 行每行 m 个整数表示矩阵。
输出描述：
输出一个整数表示答案。
示例1
输入
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
输出
12
备注：
1
≤
n
,
m
≤
2000
1 \leq n,m \leq 2000
1≤n,m≤2000
0
≤
a
i
j
≤
100
0 \leq a_{ij} \leq 100
0≤aij≤100
题解：
状态转移方程：F[i, j] = min(F[i - 1,j], F[i, j - 1]) + a[i, j]，下面逐步对它进行优化：
基础版本解法：
用另外一个空间大小为
n
×
m
n \times m
n×m 的数组进行状态更新，这样搭配原数组，空间大小为：
O
(
2
×
n
×
m
)
O(2 \times n \times m)
O(2×n×m)
基础版本解法代码：
#include <cstdio>
#include <algorithm>
using namespace std
;
const int N
= 2010;
int a
[N
][N
];
int f
[N
][N
];
int n
, m
;
void solve() {
for (int i
= 1; i
< n
; ++i
) {
for (int j
= 1; j
< m
; ++j
) {
f
[i
][j
] = min(f
[i
][j
- 1], f
[i
- 1][j
]) + a
[i
][j
];
}
}
printf("%d\n", f
[n
- 1][m
- 1]);
}
int main(void) {
scanf("%d%d", &n
, &m
);
for (int i
= 0; i
< n
; ++i
) {
for (int j
= 0; j
< m
; ++j
) {
scanf("%d", a
[i
] + j
);
if (!i
) {
f
[i
][j
] = a
[i
][j
];
if (j
) f
[i
][j
] += f
[i
][j
- 1];
}
if (!j
) {
f
[i
][j
] = a
[i
][j
];
if (i
) f
[i
][j
] += f
[i
- 1][j
];
}
}
}
solve();
return 0;
}
优化一：
我们可以直接在原数组 a 上进行更新，不需要开辟新的数组，这样能节省一些空间。
优化一代码：
#include <cstdio>
#include <algorithm>
using namespace std
;
const int N
= 2010;
int a
[N
][N
];
int f
[N
][N
];
int n
, m
;
void solve() {
for (int i
= 1; i
< n
; ++i
) {
for (int j
= 1; j
< m
; ++j
) {
f
[i
][j
] = min(f
[i
][j
- 1], f
[i
- 1][j
]) + a
[i
][j
];
}
}
printf("%d\n", f
[n
- 1][m
- 1]);
}
int main(void) {
scanf("%d%d", &n
, &m
);
for (int i
= 0; i
< n
; ++i
) {
for (int j
= 0; j
< m
; ++j
) {
scanf("%d", a
[i
] + j
);
if (!i
) {
if (j
) a
[i
][j
] += a
[i
][j
- 1];
}
if (!j
) {
if (i
) a
[i
][j
] += a
[i
- 1][j
];
}
if (i
&& j
) {
a
[i
][j
] += min(a
[i
- 1][j
], a
[i
][j
- 1]);
}
}
}
printf("%d\n", a
[n
- 1][m
- 1]);
return 0;
}
优化二：
观察状态转移方程，F[i, j] 只跟 F[i - 1, j] 和 F[i, j - 1] 有关，于是我们可以使用一个额外的数组记录上一层状态，即新的状态转移方程为：F[i] = min(F[i - 1], F[i]) + a[i,j]，其中 a[i, j] 可以在输入时处理，不用开辟一个数组去存储，这样的话，空间复杂度为
O
(
m
)
O(m)
O(m) 。
优化二代码：
#include <cstdio>
#include <algorithm>
using namespace std
;
const int N
= 2010;
const int INF
= 0x3f3f3f3f;
int n
, m
;
int f
[N
];
void solve() {
for (int i
= 1; i
<= m
; ++i
) {
scanf("%d", f
+ i
);
f
[i
] += f
[i
- 1];
}
f
[0] = INF
;
int now
;
while (n
-- > 1) {
for (int i
= 1; i
<= m
; ++i
) {
scanf("%d", &now
);
f
[i
] = now
+ min(f
[i
], f
[i
- 1]);
}
}
printf("%d\n", f
[m
]);
}
int main(void) {
scanf("%d%d", &n
, &m
);
solve();
return 0;
}
