p1004 [noip2000 提高组] 方格取数

题目描述

给定一个 $n\times m$ 的矩阵，矩阵中的每个数都是非负整数。从矩阵的左上角走到右下角，每次只能向右或向下走一步，沿途经过的数都要累加起来。请问，求出一条从左上角走到右下角的路径，使得路径经过的数之和最小，输出这个最小值。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个非负整数，表示矩阵中的一个数。

输出格式

输出一个整数，表示从左上角走到右下角的最小路径和。

数据范围

$1\le n,m\le 200$，矩阵中的数均为非负整数且不超过 $100$。

输入样例

3 3
1 3 5
2 1 3
2 2 1

输出样例

8

算法1

(动态规划) $O(nm)$

状态表示：$f[i][j]$ 表示从 $(1,1)$ 走到 $(i,j)$ 的最小路径和。

状态转移：

- $f[i][j]=\min(f[i-1][j],f[i][j-1])+a[i][j]$

时间复杂度

参考文献

python3 代码

C++ 代码

java 代码

算法2

(暴力枚举) $O(nm2^{n+m})$

blablabla

时间复杂度

参考文献

C++ 代码