洛谷P8612的多方法实现（dfs和记忆化搜索）

洛谷P8612的多方法实现

题目描述

X 国王有一个地宫宝库。是 $n \times m$ 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 $k$ 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 $k$ 件宝贝。

输入格式

输入一行 $3$ 个整数，用空格分开：$n$，$m$，$k(1 \le n,m \le 50,1 \le k \le 12)$。

接下来有 $n$ 行数据，每行有 $m$ 个整数 $C_i(0 \le C_i \le 12)$ 代表这个格子上的宝物的价值。

输出格式

要求输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。该数字可能很大，输出它对 $1000000007(10^9+7)$ 取模的结果。

输入输出样例 #1

输入 #1

2 2 2
1 2
2 1

输出 #1

2

输入输出样例 #2

输入 #2

2 3 2
1 2 3
2 1 5

输出 #2

14

说明/提示

时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛

解决方案

DFS

在看到这道题目的时候我们可以很自然地想到使用搜索的方法，那么DFS的写法如下所示：

import sys
sys.setrecursionlimit(1000000)

dirs = [(0, 1), (1, 0)]
ans = 0

def dfs(x, y, count, maxi): 
  # 用count来记录已经捡起来的宝物数
  # 用maxi来记录已经捡起来的宝物中最高的价值
  global ans

  if not (0 <= x < n and 0 <= y < m):
    return 
  if x == n-1 and y == m-1:
    # 有两种情况可以满足走到出口时小明正好有k件宝贝
    # 一种是在这之前已经拿到了k件宝贝
    # 另一种是恰好在出口处捡到了第k件宝贝
    if count == k or (count == k-1 and arr[x][y] > maxi):
      ans += 1
      return 

  # 开始搜索，一共有四种情况：向下拿，向右拿，向下不拿，向右不拿
  for dx, dy in dirs:
    nx, ny = x + dx, y + dy
    # 不拿
    dfs(nx, ny, count, maxi)
    # 拿
    if arr[x][y] > maxi:
      dfs(nx, ny, count+1, arr[x][y])


if __name__ == "__main__":
  n, m, k = map(int, input().split())
  
  arr = [[0 for i in range(m+1)] for j in range(n+1)]
  for i in range(n):
    ls = list(map(int, input().split()))
    for j in range(m):
      arr[i][j] = ls[j]

  dfs(0, 0, 0, -1)
  print(ans % 1000000007)

但是这种写法只能拿到42分，说明这种写法的时间复杂度还是比较高的，那么接下来我们尝试记忆化搜索的写法。

记忆化搜索

所谓记忆化搜索就是将先前的搜索结果记录到一个数组当中，如果后续再次遇到相同的情景直接读取之前记录的结果即可，这将大大简化搜索过程，在这道题的情境下记忆化搜索的写法如下所示：

dirs = [(0, 1), (1, 0)]
# Python中用_来表示不被关心的变量，在这里用其长短变化可以较为直观地显示出层级变化
mem = [[[[-1 for _ in range(15)] for __ in range(15)] for ___ in range(55)] for ____ in range(55)]

def dfs_memory(x, y, count, maxi):
  ans = 0

  # 说明已经被记录过
  if mem[x][y][count][maxi] != -1:
    return mem[x][y][count][maxi]

  if not (0 <= x < n and 0 <= y < m):
    return 0
  if x == n-1 and y == m-1:
    if count == k or (count == k-1 and arr[x][y] > maxi):
      ans += 1

  # 开始搜索
  for dx, dy in dirs:
    nx, ny = x + dx, y + dy
    ans += dfs_memory(nx, ny, count, maxi)
    if arr[x][y] > maxi:
      ans += dfs_memory(nx, ny, count+1, arr[x][y])

  mem[x][y][count][maxi] = ans % 1000000007
  return mem[x][y][count][maxi]



if __name__ == "__main__":
  n, m, k = map(int, input().split())

  arr = [[0 for i in range(m+1)] for j in range(n+1)]
  for i in range(n):
    ls = list(map(int, input().split()))
    for j in range(m):
      arr[i][j] = ls[j]

  ans = dfs_memory(0, 0, 0, -1)
  print(ans % 1000000007)

Bingo！并且可以发现运行时间大幅减少：

动态规划