hdu 1078 FatMouse and Cheese(记忆化搜索)

hdu 1078 FatMouse and Cheese(记忆化搜索)

Hdu 1078题目中的"FatMouse and Cheese"这个名字相信很多ACMer都耳熟能详了。它是一个典型的记忆化搜索题目，用来考察动态规划和递归的知识。下面就来详细解析这道题目。

1. 题目描述

1.1 题目背景

FatMouse是一只胖老鼠，住在一个有很多房间的迷宫中。每个房间都有一个特定的权值，抓到老鼠，可以获得该房间的权值。老鼠每次只能从一个房间跳到另一个房间，且只能跳到权值不小于当前房间权值的房间中。现在，给定起点房间的权值，要求老鼠找到一条路径，使得获得的总权值最大。

1.2 输入格式

输入包含多组测试样例。每组测试样例的第一行为两个整数n和m，表示迷宫的行数和列数。接下来n行，每行包含m个整数，表示每个房间的权值。当输入n=0，m=0时，表示输入结束。

1.3 输出格式

对每组测试样例，输出一行，包含一个整数，表示老鼠最大能获取的权值。

1.4 样例输入输出

输入：

1 2

1 2
1 3
2 3
0 0

输出：

4

2. 解题思路

2.1 动态规划

本题可以用动态规划的思想来解决。定义一个dp数组，dp[i][j]表示从起点到达(i,j)房间所能获取的最大权值。则状态转移方程为：

dp[i][j] = max(dp[a][b] + 1)，其中(a,b)为可以从(i,j)跳到的房间

由于当前房间的权值必须大于等于前一房间的权值，所以可以通过遍历前一房间的四个方向来找到可以从当前房间跳到的房间。

需要注意的是，由于题目要求求解的路径是逆向的，即从终点到起点，所以初始状态应当为终点房间的权值，终点房间的权值需要预处理一下。

2.2 记忆化搜索

为了避免重复计算，可以使用记忆化搜索来优化算法。在计算过程中，每次将计算得到的dp[i][j]保存下来，下次再计算时，先判断一下是否计算过，如果计算过，则直接返回结果。这样可以大大减少不必要的计算，提高算法的效率。

3. 代码实现

# 定义dp数组，默认初始为-1

dp = [[-1] * m for _ in range(n)]
def dfs(i, j):
    # 如果已经计算过，直接返回结果
    if dp[i][j] != -1:
        return dp[i][j]
    # 如果到达起点，最大权值就是起点房间的权值
    if i == 0 and j == 0:
        return rooms[i][j]
    # 计算可以跳到的房间的最大权值
    max_value = 0
    for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if 0 <= x < n and 0 <= y < m and rooms[x][y] >= rooms[i][j]:
            max_value = max(max_value, dfs(x, y) + rooms[x][y])
    # 将结果保存下来
    dp[i][j] = max_value
    return max_value
# 处理多组测试样例
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    rooms = [list(map(int, input().split())) for _ in range(n)]
    # 预处理终点房间的权值
    rooms[n-1][m-1] += rooms[0][0]
    # 初始化dp数组
    dp = [[-1] * m for _ in range(n)]
    # 调用dfs函数进行记忆化搜索
    max_value = dfs(n-1, m-1)
    print(max_value)

4. 总结

记忆化搜索是一种优化动态规划的常用手段，可以提高算法的效率。在解决类似问题时，可以考虑使用记忆化搜索来避免重复计算。对于本题，通过使用记忆化搜索，可以在给定时间内求解出最优解。