[POJ1088] 滑雪(递归dp)

题目描述

给出一个$n\times m$的矩阵，每个位置上有一个非负整数，代表这个位置的海拔高度。一开始时，有一个人站在其中一个位置上。这个人可以向上、下、左、右四个方向移动，但是只能移动到海拔高度比当前位置低或者相等的位置上。一次移动只能移动一个单位长度。定义一个位置为“山顶”，当且仅当从这个位置开始移动，可以一直走到海拔高度比它低的位置上。请问，这个矩阵中最多有多少个“山顶”？

输入格式

第一行两个整数，分别表示$n$和$m$。

接下来$n$行，每行$m$个整数，表示整个矩阵。

输出格式

输出一个整数，表示最多有多少个“山顶”。

样例输入

4 4
3 2 1 4
2 3 4 3
5 6 7 8
4 5 6 7

样例输出

5

算法1

(递归dp) $O(nm)$

对于这道题，我们可以使用递归DP来解决，用$f(i,j)$表示以$(i,j)$为起点的路径最大长度，那么最后的答案就是所有$f(i,j)$中的最大值。

状态转移方程如下：

$$
f(i,j)=\max f(x,y)+1(x,y)是(i,j)的下一个满足条件的位置
$$

注意：这里的状态转移方程中的$x,y$是在枚举四个方向时得到的下一个位置，即：

- 向上：$(i-1,j)$
- 向下：$(i+1,j)$
- 向左：$(i,j-1)$
- 向右：$(i,j+1)$

实现过程中需要注意以下几点：

- 每个点都需要搜一遍，因此需要用双重for循环来枚举每个起点；
- 对于已经搜索过的点，需要用一个数组$vis$来记录，防止重复搜索；
- 在进行状态转移时，需要判断移动后的点是否满足条件。

时间复杂度

状态数为$O(nm)$，每个状态转移的时间复杂度为$O(1)$，因此总时间复杂度为$O(nm)$。

参考文献

C++ 代码

算法2

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

动态规划的思路与递归DP类似，只不过转移方程和实现方式有所不同。

状态转移方程如下：

$$
f(i,j)=\max f(x,y)+1(x,y)是(i,j)的下一个满足条件的位置
$$

注意：这里的状态转移方程中的$x,y$是在枚举四个方向时得到的下一个位置，即：

- 向上：$(i-1,j)$
- 向下：$(i+1,j)$
- 向左：$(i,j-1)$
- 向右：$(i,j+1)$

实现过程中需要注意以下几点：

- 每个点都需要搜一遍，因此需要用双重for循环来枚举每个起点；
- 对于已经搜索过的点，需要用一个数组$vis$来记录，防止重复搜索；
- 在进行状态转移时，需要判断移动后的点是否满足条件。

时间复杂度

状态数为$O(nm)$，每个状态转移的时间复杂度为$O(1)$，因此总时间复杂度为$O(nm)$。

参考文献

C++ 代码