蓝桥杯2022年第十三届省赛真题-李白打酒加强版（基于记忆数组的动态规划）

首先构建DFS搜索的函数：long long DFS(long long n, long long m, long long liquor)。这里n代表已经遇到店的次数，m代表已经遇到花的次数，liquor代表当前李白有多少酒。然后设N、M为李白需要遇到店和花的次数，针对每次的n、m、liquor三个参数，根据以下规则进行剪枝：

1、遇到店和花的次数都不能超限；

2、酒空时不能遇花，即liquor的范围与花一致，都在[0，M]；

3、当遇完所有店时，壶中liquor需与剩余遇花数（M-m）一致；

4、确保最后一次遇到花且酒空，此时n和m应该达到上限；

5、最后遇到的花，不存在中途酒空的情况。

以上剪枝可能复杂了些，但出于考虑到避免出现越界等运行错误，因此实现全部约束参考代码如下:

    if (n == N && m == M && liquor == 0)
        return 1;
    else if (m == M && n < N)
        return 0;
    else if (n == N && (M - m) > liquor)
        return 0;
    else if (n > N || m > M)
        return 0;
    else if (liquor < 0 || liquor > M)
        return 0;
    else if (liquor == 0 && (n != N && m != M))
        return 0;

然后给出DFS的状态转移方程：DFS(n,m,liquor) = DFS(n+1,m,liquor*2) + DFS(n,m+1,liquor-1)。

基于该状态转移方程和剪枝只拿到了48分，因此引入一个三维记忆数组，DP[N][M][M]，用于记录DFS的每种状态，如果已经计算过该状态则直接返回数组对应下标的元素值，如果没有计算过该状态则按DFS的方法计算该状态并将结果保存在记忆数组中。从而避免了重复计算状态引发的时间损耗，让时间复杂度从O(2^(N+M))降低为O(N*M^2)，虽然还是三次方级别的，但是通过本题已经绰绰有余了。最终合并上述思路，给出代码：

#include <iostream>
using namespace std;

long long N, M;
long long dp[150][150][150];
long long DFS(long long n, long long m, long long liquor);

int main()
{
    cin >> N >> M;
    for (int i = 0; i < 150; i ++)
        for (int j = 0; j < 150; j ++)
            for (int k = 0; k < 150; k ++)
                dp[i][j][k] = -1;
    cout << DFS(0, 0, 2) % 1000000007 << endl;
    return 0;
}

long long DFS(long long n, long long m, long long liquor)
{
    long long num = 0;
    if (n == N && m == M && liquor == 0)
        return 1;
    else if (m == M && n < N)
        return 0;
    else if (n == N && (M - m) > liquor)
        return 0;
    else if (n > N || m > M)
        return 0;
    else if (liquor < 0 || liquor > M)
        return 0;
    else if (liquor == 0 && (n != N && m != M))
        return 0;
    if (dp[n][m][liquor] != -1)
        return dp[n][m][liquor];
    num = (num + DFS(n, m + 1, liquor - 1)) % 1000000007;
    num = (num + DFS(n + 1, m, liquor * 2)) % 1000000007;
    dp[n][m][liquor] = num;
    return num;
}

需要特别的是，”if (dp[n][m][liquor] != -1)“该语句块必须写在剪枝下面，否则没有剪枝的保护n可能会大于N从而导致数组的指针越界（其他变量也一样）。采用这种方法就可以通过全部用例。运行结果如下：

这种损耗空间来换取时间的方式在竞赛和考试中很常用。