解题思路
这题有两种思路:DFS
和线性dp
。
$dfs$的时间复杂度为$O(2^n)$肯定是超时的,如果用三重$dp$来记录三种状态,那么时间复杂度是$O(n^3)$可以过$100\%$的样例。两种方法的代码都给出,以供参考。
动态规划做法
part1
动态规划的题先想状态转移方程,根据题意遇到店$n$次,遇到花$m$次,酒壶有多少酒,显然我们可以用三重$dp$来记录三种状态。$dp[i][j][k]$表示遇到了$i$次店、$j$次花,酒壶里还剩$k$斗酒。
part2
状态转移方程:$dp[i][j][k] = dp[i-1][j][k\div2]+dp[i][j-1][k+1]$
part3
$dp[i-1][j][k\div2]$表示如果李白这次遇到的是店,那么可以从上一次遇店次数$i-1$的方程转移过来,因为每次遇店后酒翻一倍所以上一次的酒是$k\div2$。$dp[i][j-1][k+1]$表示这次遇到的是花,同理。
part4
需要注意的是,$k$为偶数的时候才能从$k\div2$转移过来,为奇数的时候说明上一次遇到的一定是花。由题可知最后一次遇到的是花,所以答案取:$dp[n][m-1][1]$。
参考代码
动态规划代码(过100%)
n, m = map(int, input().split())
N = 110; mod = 10**9 + 7
dp = [[[0] * N for i in range(N)] for i in range(N)]
dp[0][0][2] = 1 # 初始化dp
for i in range(n + 1):
for j in range(m + 1):
for k in range(m + 1):
if i == 0 and j == 0: continue
if i and k % 2 == 0: dp[i][j][k] += dp[i-1][j][k//2] % mod
if j: dp[i][j][k] += dp[i][j-1][k+1] % mod
print(dp[n][m-1][1] % mod)
dfs代码(过40%)
import sys
from functools import lru_cache
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
mod = 10**9 + 7
ans = 0
lru_cache(maxsize=None) # 记忆化搜索
def dfs(a, b, e):
global ans
if a == n and b == m - 1 and e == 1:
ans += 1
return
if e <= 0 and a != n: return # 如果酒已经没了,但是还有花,则不合法
if a < n: dfs(a+1, b, e*2) # 遇到了店
if b < m: dfs(a, b+1, e-1) # 遇到了花
dfs(0, 0, 2)
print(ans % mod)