动态规划（偏难）：李白打酒加强版-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划（偏难）：李白打酒加强版。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

李白打酒加强版

问题描述

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:

无事街上走，提显去打酒。
逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 $N$ 次, 遇到花 $M$ 次。已知最后一次遇到的是花, 他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇花是不合法的。

输入格式

第一行包含两个整数 $N$ 和 $M$ .

输出格式

输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果.

样例输入

5 10

样例输出

样例说明

如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

评测用例规模与约定

对于 $\\%$ 的评测用例: $\leq N, M \leq 10$ 。

对于 $\\%$ 的评测用例: $\leq N, M \leq 100$ 。

解题思路

由于 $N, M$ 最大值为100，要满足题目要求——在最后一次将酒喝完，则说明酒的上限不会超过 $M$ 。

总共存在 $N + M$ 次相遇，每次相遇存在两种可能性，如果暴力枚举所有可能性，时间复杂度为 $2^{N+M}$ ，无法通过。

背包问题，每件物品存在“取”和“不取”两种可能，取之后根据物品的体积和价值进行更新。
$V S$
相遇，最终需要经过 $N$ 次店， $M$ 次花

此处对应着相遇是否为“店”和“花”：

如果是花，则花的数量 $+ 1$ ，酒 $- 1$
如果是店，则店的数量 $+ 1$ ，酒 $* 2$

定义 $d p [i] [j] [k]$ 表示第 $i$ 次相遇，每次相遇需要维护店的数量 $j$ （或花的数量 $i - j$ ，维护其中一个即可），酒量为 $k$ 的方案数。

题目要求的是“遇到店 $N$ 次, 遇到花 $M$ 次，最后一次遇到的是花，正好把酒喝光”的方案数。也就相当于在前 $N + M - 1$ 次中，遇到店 $N$ 次，酒量为 $1$ 的方案数（ $d p [N + M - 1] [N] [1]$ ），因为此时最后遇到花才能恰好喝完。

$d p$ 数组的动态转移方程：

初始时从家中出来有 $2$ 斗酒，可以表示为边界情况 $d p [0] [0] [2] = 1$
如果第 $i$ 次相遇为花，则 $d p [i] [j] [k]$ 可以由 $d p [i - 1] [j] [k + 1]$ 转移过来，相当于前 $i - 1$ 次相遇中店铺为 $j$ 次、酒量为 $k + 1$ ，第 $i$ 次为花则店铺数量不变，酒量数量减一。
如果第 $i$ 次相遇为店，则 $d p [i] [j] [k]$ 中的 $k$ 必须为偶数，此时从 $d p [i - 1] [j - 1] [k /2]$ 转移过来。

根据上述分析，可以根据 $k$ 的奇偶性和转移方程更新 $d p$ 数组。

实现时注意防止计算溢出。文章来源地址https://www.toymoban.com/news/detail-499794.html

AC_Code（Python3-不用滚动数组优化）

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
MOD=int(1e9+7)
dp=[[[0]*110 for i in range(110)] for j in range(210)]

n,m=map(int,input().split())
dp[0][0][2]=1
for i in range(1,n+m):
    for j in range(0,n+1):
        for k in range(0,m+1):
            if j!=0 and k%2==0:
                dp[i][j][k]=(dp[i-1][j][k+1]+dp[i-1][j-1][k//2])%MOD
            else:
                dp[i][j][k]=dp[i-1][j][k+1]
print(dp[n+m-1][n][1])

AC_Code（Python3-交替滚动数组优化）

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
MOD=int(1e9+7)
dp=[[[0]*110 for i in range(110)] for j in range(2)]
n,m=map(int,input().split())
dp[0][0][2]=1
new = 1
old = 0
for i in range(1,n+m):
    old,new = new,old
    for j in range(0,n+1):
        for k in range(0,m+1):
            if j!=0 and k%2==0:
                dp[new][j][k]=(dp[old][j][k+1]+dp[old][j-1][k//2])%MOD

            else:
                dp[new][j][k]=dp[old][j][k+1]
print(dp[new][n][1])

AC_Code（Python3-自身滚动数组优化）

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
MOD=int(1e9+7)
dp=[[0]*110 for i in range(110)]
n,m=map(int,input().split())
dp[0][2]=1
for i in range(1,n+m):
    for j in range(n,-1,-1):
        for k in range(0,m+1):
            if j!=0 and k%2==0:
                dp[j][k]=(dp[j][k+1]+dp[j-1][k//2])
            else:
                dp[j][k]=dp[j][k+1]
print(dp[n][1])