地宫取宝与记忆型递归算法解析

"地宫取宝与记忆型递归是一个典型的动态规划问题，结合了记忆化搜索的方法来解决。此问题来源于蓝桥杯算法竞赛，旨在考察选手的编程能力和算法理解能力。" 在这个问题中，我们需要帮助小明计算在特定条件下，通过不同路径选取k件宝藏的方案数。地宫是一个n x m的网格，每格都有一个价值Ci的宝藏，小明只能向右或向下移动，并且只有当新发现的宝藏价值大于他当前手中所有宝藏的最高价值时，他才会选择拾取。目标是找到恰好持有k件宝藏到达出口的路径数量。 首先，我们定义了4维的动态规划数组`mem`，用于存储已经计算过的状态，避免重复计算，提高效率。数组的四个维度分别是当前位置的x坐标、y坐标、当前背包中最大宝藏价值和已收集的宝藏数量。 `Search`函数是核心的递归函数，它接收四个参数：当前位置的x、y坐标，当前背包能装的最大宝藏价值`max`，以及已收集的宝藏数量`cnt`。在函数开始时，我们检查`mem`数组是否已经存储了当前位置的状态，如果存在则直接返回结果，这是记忆化搜索的关键步骤。 接着，我们处理边界条件：当小明到达出口时，如果他已经收集了k件宝藏，或者如果他能在下一个格子收集到第k件宝藏，这两种情况下都增加计数器`ans`。同时，为了避免答案溢出，我们需要对答案取模1000000007。 在满足条件的情况下，我们考虑两种情况：一是当前格子的宝藏价值大于`max`，那么小明会选择这个宝藏，因此我们需要在向下和向右两个方向分别进行递归搜索，此时背包最大值更新为当前格子的宝藏价值，且宝藏数量加一。二是当前格子的宝藏价值不大于`max`，小明不会选择这个宝藏，那么他在向下和向右两个方向进行递归搜索时，背包最大值和宝藏数量保持不变。 最后，将四个递归子问题的结果相加，得到当前位置的总方案数，并返回。 样例输入和输出展示了不同情况下，小明可以采取的不同策略数量。通过递归和记忆化搜索，我们可以有效地计算出这个问题的解决方案，避免了暴力递归导致的时间复杂度过高问题。在实际编程时，应确保正确初始化`mem`数组，并在递归调用之前检查缓存，以提高程序运行速度。