李白打酒的三种解法

题目描述
话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：

无事街上走，提壶去打酒。

逢店加一倍，遇花喝一斗。

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

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

注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

输入格式
第一行包含两个整数 N 和 M.

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

样例输入
5 10
样例输出
14
提示
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
对于 40% 的评测用例：1 ≤ N, M ≤ 10。
对于 100% 的评测用例：1 ≤ N, M ≤ 100。

//法一：dfs暴力，时间复杂度O(2^n)

#include <iostream>

const int MOD = 1e9 + 7;

int dfs(int n, int m, int b) {
    if (!n && !m && !b) {
        return 1;
    }
　　 //b不能等于0，因为题目要求最后一次要遇到花，所以在此之前酒不能变为0
    if (n < 0 || m < 0 || b <= 0 || b > m) {
        return 0;
    }
    return (dfs(n - 1, m, 2 * b) % MOD + dfs(n, m - 1, b - 1) %MOD) %MOD;
}

int main() {
    int n, m, b = 2;
    std::cin >> n >> m;
    std::cout << dfs(n, m, b) << std::endl;
    return 0;
}

//法二：记忆化搜索：时间复杂度O(n*m^2)

#include <iostream>

const int MOD = 1e9 + 7;
//map用来记录递归到终点的部分字段结果，保存后用来避免重复计算
std::unordered_map<int, std::unordered_map<int, std::unordered_map<int, long long>>> mp;

int dfs(int n, int m, int b)
{
    if (mp[n][m].count(b)) {
        return mp[n][m][b];
    }
    if (n < 0 || m < 0 || b <= 0 || b > m) {
        return mp[n][m][b] = 0;
    }
    return mp[n][m][b] = (dfs(n - 1, m, 2 * b) + dfs(n, m - 1, b - 1)) % MOD;
}

int main()
{
    int n, m;
    std::cin >> n >> m;
    mp[0][0][0] = 1;
    std::cout << dfs(n, m, 2) << std::endl;
    return 0;
}

//法三：动态规划，时间复杂度O（n*m^2）,但是因为没有使用hashmap，少了很多内存分配与查询的开销，速度提高显著

#include <iostream>
const int N = 110;，
const int MOD = 1e9 + 7;

//dp(i, j, k)表示遇到i家店，j次花，拥有k斗酒的路径条数
long long dp[N][N][N];

int main()
{
    int n, m;
    std::cin >> n >> m;
    dp[0][0][2] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m - j; k++) {
                if (!(k & 1) && i) {
                    dp[i][j][k] = dp[i - 1][j][k >> 1];
                }
                if (j) {
                    dp[i][j][k] += dp[i][j - 1][k + 1];
                }
                dp[i][j][k] %= MOD;
            }
        }
    }
    std::cout << dp[n][m - 1][1] << std::endl;
    return 0;
}