01088: 滑雪
dp, dfs similar, http://cs101.openjudge.cn/practice/01088
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
输入
输入的第一行表示区域的行数R和列数C(1 ≤ R,C ≤ 100)。下面是R行，每行有C个整数，代表高度h，0≤ h≤ 10000。
输出
输出最长区域的长度。
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9样例输出
25来源：USACO
python
"""
算法基础与在线实践：
递推的顺序是，讲所有点按高度从小到大排序，然后按照高度从小到大计算所有点的L值。
计算点(i,j)时，与它相邻的比它低的点必然已经计算过，因此可以递推
"""
import heapq
rows, cols = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(rows)]
# 使用最小堆存储元素及其坐标
heap = [(matrix[i][j], i, j) for i in range(rows) for j in range(cols)]
heapq.heapify(heap)
# 每个点的L值初始化为1
dp = [[1] * cols for _ in range(rows)]
# 定义方向数组，用于遍历上下左右
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 记录最长递增路径长度
longest_path = 1
# 遍历堆中的元素，按高度从小到大处理
while heap:
height, x, y = heapq.heappop(heap)
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and matrix[nx][ny] < height:
dp[x][y] = max(dp[x][y], dp[nx][ny] + 1)
longest_path = max(longest_path, dp[x][y])
print(longest_path)可以用 sort 代替 heapq，因为 heapq 的主要优势是动态获取最小/最大值，而这里并不需要动态插入或删除元素。我们只需按照高度从小到大处理所有点，使用排序即可实现相同的逻辑。
python
rows, cols = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(rows)]
# 将所有点按高度从小到大排序
points = sorted([(matrix[i][j], i, j) for i in range(rows) for j in range(cols)])
# 每个点的L值初始化为1
dp = [[1] * cols for _ in range(rows)]
# 定义方向数组，用于遍历上下左右
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 记录最长递增路径长度
longest_path = 1
# 从低到高，前面的不会对后面造成影响！
for height, x, y in points:
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and matrix[nx][ny] < height:
dp[x][y] = max(dp[x][y], dp[nx][ny] + 1)
longest_path = max(longest_path, dp[x][y])
print(longest_path)dfs即可，状态相同的位置的搜索结果永远相同，故可以用数组记录（进而只用搜索一次）（其实本质就是@lru_cache(maxsize=None)，因此也可以只用这一行语句解决）
python
import sys
sys.setrecursionlimit(1 << 30)
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(x, y):
if d[x][y] > 0: return d[x][y]
ans = 1
for nx, ny in directions:
tx, ty = x + nx, y + ny
if 0 <= tx < n and 0 <= ty < m and a[tx][ty] < a[x][y]:
ans = max(ans, dfs(tx, ty) + 1)
d[x][y] = ans
return ans
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
d = [[0] * m for _ in range(n)]
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ans = 1
for i in range(n):
for j in range(m):
ans = max(ans, dfs(i, j))
print(ans)思路：dp+dfs，遍历矩阵，将尚未dfs过的地方dfs，在dp数组中记录此处数值
python
r, c = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(r)]
dp = [[0 for _ in range(c)] for _ in range(r)]
def dfs(x, y):
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < r and 0 <= ny < c and matrix[x][y] > matrix[nx][ny]:
if dp[nx][ny] == 0:
dfs(nx, ny)
dp[x][y] = max(dp[x][y], dp[nx][ny] + 1)
if dp[x][y] == 0:
dp[x][y] = 1
ans = 0
for o in range(r):
for j in range(c):
if not dp[o][j]:
dfs(o, j)
ans = max(ans, dp[o][j])
print(ans)思路：辅助栈
python
# 李佳聪 24工学院
a, b = map(int, input().split())
matrix = [[10001] * (b + 2)]
for i in range(a):
matrix.append([10001] + list(map(int, input().split())) + [10001])
matrix.append([10001] * (b + 2))
dp = [[1 for i in range(b + 2)] for i in range(a + 2)]
stack = []
for i in range(1, a + 1):
for j in range(1, b + 1):
stack.append((matrix[i][j], i, j))
stack.sort(reverse=True)
dire = [(0, 1), (1, 0), (0, -1), (-1, 0)]
for high, x, y in stack:
for xi, yi in dire:
if matrix[x + xi][y + yi] < matrix[x][y]:
dp[x + xi][y + yi] = max(dp[x + xi][y + yi], dp[x][y] + 1)
output = 0
for i in range(a):
for j in range(b):
output = max(output, dp[i][j])
print(output)思路：用一个2d list作为记录经过路径长(dp)，起始都为0。然后dfs，如果如果dp[i][j]大于0，就是已经检验过最长经过路径，所以return dp[i][j]；否则代表是第一次检验，检查上下左右的格子，如果高度小就可以走，返回max{dp[i][j], 四周的格的dfs + 1}。
【刘安澜，2020年秋】我对老师的代码进行了一个改进，因为本题说高度最大值不超过10000，所以保护圈元素取10001即可满足不超过边界，这样函数更加简洁。
【李元锋，2020年秋】正常思路是从第一个元素开始，判断滑雪最长距离，过一遍。但这里有很多重复计算的子问题，所以引入 dp函数，如果坐标周围有比自己低的坡道，判断滑哪条周围的坡道最长就滑哪条。然后直接遍历一遍二维数组即可，这里要添加保护圈以防万一滑出边界。
python
r, c = map(int, input().split())
node = [] # height of each element
node.append( [100001 for _ in range(c+2)] )
for _ in range(r):
node.append([100001] +[int(_) for _ in input().split()] + [100001])
node.append( [100001 for _ in range(c+2)] )
dp = [[0]*(c+2) for _ in range(r+2)]
dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0,-1]
def dfs(i,j):
if dp[i][j]>0:
return dp[i][j]
for k in range(4):
if node[i+dx[k]][j+dy[k]] < node[i][j]:
dp[i][j] = max( dp[i][j], dfs(i+dx[k], j+dy[k])+1 )
return dp[i][j]
ans = 0
for i in range(1, r+1):
for j in range(1, c+1):
ans = max( ans, dfs(i,j) )
print(ans+1)【王康安，2020年秋】。虽然开了个叫 dp的数组，但我感觉解法其实更像贪心。刚巧昨天在 OJ上写了一道 Huffman树的题（OJ18164：剪绳子），这里我的策略就很相似。把所有区域的高度和坐标存到一个栈里，排序，每次都把栈内高度最高的区域弹出去并处理。当前这个区域是到不了那些之前已经弹出的，比当前这个区域更高的区域的，也就是说，之前那些区域都不会影响这一步的策略，具有无后效性和最优子结构性质。状态转移方程非常直白就不多说了。上代码，毕竟没有按 dfs去写所以标了注释：
python
r,c = [int(x) for x in input().split()]
rgn = [[20000]*(c+2)]
for i in range(r):
rgn.append([20000]+[int(x) for x in input().split()]+[20000])
rgn.append([20000]*(c+2)) #读入上保护圈方便处理边界情况
stack = []
for i in range(1,r+1):
for j in range(1,c+1):
stack.append([rgn[i][j], i, j])
stack.sort() #所有节点按从小到大排序
loc = [[1,0],[-1,0],[0,1],[0,-1]] #方向数组
dp = [[1]*(c+2) for x in range(r+2)] #dp数组初始化全为1 上保护圈只是为了和rgn数组下标保持一致
while stack != []:
temp = stack.pop() #用temp数组保存出栈值该值也是当前栈内最大值
for i in range(4):
if rgn[temp[1]+loc[i][0]][temp[2]+loc[i][1]]<rgn[temp[1]][temp[2]]:
#由于是栈内最大值此条件一定成立这里仅是为了处理保护圈情况
dp[temp[1]+loc[i][0]][temp[2]+loc[i][1]] = \
max(dp[temp[1]+loc[i][0]][temp[2]+loc[i][1]],dp[temp[1]][temp[2]]+1)
#状态转移方程
out = 0
for i in range(1,r+1):
out = max(out,max(dp[i]))
print(out)思路：这是知乎上搜的图论算法：按入度作拓扑排序，然后按拓扑排序的顺序作dp
python
r, c = map(int, input().split())
height = []
for _ in range(0, r): height.append(list(map(int, input().split())))
from collections import deque, defaultdict
def neighbour(i, j):
lst = []
directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}
for dx, dy in directions:
if 0 <= i + dx < r and 0 <= j + dy < c:
lst.append((i + dx, j + dy))
return lst
queue = deque()
deg = defaultdict(int)
for i in range(0, r):
for j in range(0, c):
deg[(i, j)] = sum([int(height[i][j] > height[x][y]) for (x, y) in neighbour(i, j)])
if deg[(i, j)] == 0:
queue.append((i, j))
step = 0
while queue:
for _ in range(0, len(queue)):
x, y = queue.popleft()
for nx, ny in neighbour(x, y):
if height[nx][ny] > height[x][y]:
deg[(nx, ny)] -= 1
if deg[(nx, ny)] == 0:
queue.append((nx, ny))
step += 1
print(step)这个代码是一个解决滑雪问题的动态规划（DP）+拓扑排序实现，解决的是一个以高度为标准的最长下降路径问题。
问题描述
一个
的矩阵，元素表示高度。可以从一个点滑到比当前点低的相邻点（上下左右），目标是找到从某个点开始可以滑动的最长路径。 思路
- 拓扑排序：
- 把矩阵中的每个点视为一个图中的节点。
- 如果某点高度大于某相邻点高度，则有一条从高点指向低点的边。
- 基于这个规则，我们对整个矩阵建立一个有向无环图（DAG）。
- DAG 的性质是可以进行拓扑排序。
- 动态规划（DP）：
- 在拓扑排序的基础上，用 DP 记录以每个点为起点的最长路径长度。
- 按拓扑排序的顺序更新 DP 值。
- 实现：
- 使用入度（
deg）记录每个点的入边数量。- 入度为零的点可以直接加入队列（拓扑排序的起点）。
- 每次处理一个点时，更新相邻点的入度，同时更新最长路径的步数。
构建 DAG 和初始化入度
pythonqueue = deque() deg = defaultdict(int) for i in range(0, r): for j in range(0, c): deg[(i, j)] = sum([int(height[i][j] > height[x][y]) for (x, y) in neighbour(i, j)]) if deg[(i, j)] == 0: queue.append((i, j))
deg[(i, j)]记录点 (i, j) 的入度，即比它低的邻居数量。- 入度为 0 的点加入队列
queue，作为拓扑排序的起点。拓扑排序和动态规划
pythonstep = 0 while queue: for _ in range(0, len(queue)): x, y = queue.popleft() for nx, ny in neighbour(x, y): if height[nx][ny] > height[x][y]: deg[(nx, ny)] -= 1 if deg[(nx, ny)] == 0: queue.append((nx, ny)) step += 1
- 每次从
queue取出当前层的所有节点（拓扑排序的一层）。- 更新相邻节点的入度，如果某个相邻点入度变为 0，则加入
queue。- 每处理一层，路径长度（
step）增加 1。算法分析
- 时间复杂度：
- 邻居函数执行
次，每次计算邻居最多花费常数时间。 - 主循环中，每个点最多进队和出队一次，总复杂度为
。 - 空间复杂度：
- 额外的空间用于存储
deg和queue，复杂度为。 核心思想总结
- 拓扑排序 用于处理依赖关系，确保先处理高点，再处理低点。
- 动态规划 在拓扑排序的基础上更新最长路径。
- 这是一种典型的 DAG + DP 模式，非常适合解决矩阵中的路径问题。