0x50动态规划-(2)-DP - Be Grinder,for Better

DP

PPT：https://docs.google.com/presentation/d/1F_Qp3kzw7jZkPpb7ll7J6-02285bCA3Z9nmU1e7a2rk/edit#slide=id.g8285dd8f3f_1_512

对应视频讲解： https://www.bilibili.com/video/BV1gf4y1i78H/?vd_source=2100aa14287ae4387e91fc75d3371399

动态规划的本质是求拓扑序

DAG DP => 有向图DP

数字三角形 DP

单序列DP

最长递增子序列

双序列DP

最长公共子序列

编辑距离

状态机DP

股票买卖系列

下面是讲记忆化搜和DP之间的转换

是全局最优解一定能够拆成子问题的最优解，并且子问题和全局问题是同一类型的问题，从而递推解决

掷骰子模拟：https://leetcode.cn/problems/dice-roll-simulation 2008分

这道题分别用dfs、记忆化搜索、dp来做

dfs、记忆化搜索属于递归方法，dp属于递推方法

dfs

dfs的三个参数

剩余投掷次数，用i表示;
上一个骰子的值，用last表示;
上一个骰子的剩余连续出现次数，用left表示

class Solution {
    const int MOD = 1e9 + 7;
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        function<int(int, int, int)> dfs = [&](int i, int last, int left) -> int {
            if (i == 0) return 1; // 找到一个合法结果
            long long res = 0;
            for (int j = 0; j < 6; j ++) {
                if (j != last) res += dfs(i - 1, j, rollMax[j] - 1);
                else if (j == last && left > 0) res += dfs(i - 1, j, left - 1);
            }
            res %= MOD;
            return res;
        };

        long long res = 0;
        for (int j = 0; j < 6; j ++) {
            res += dfs(n - 1, j, rollMax[j] - 1);
        }
        res %= MOD;
        return res;
    }
};

记忆化搜索

dfs可以用记忆化搜索来优化

如果一个状态(递归入参)是第一次遇到，那么可以在返回前把状态及其结果记到一个 $cache$ 哈希表(数组)中；
如果一个状态不是第一次遇到，那么直接返回 $cache$ 中保存的结果。

这道题在leetcode上，cache用数组可以过，用哈希表会超时(因为hash函数的构造不满足结果的冲突)。

记忆化数组代码:

class Solution {
    const int MOD = 1e9 + 7;
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        int cache[n][6][15];
        memset(cache, -1, sizeof(cache)); // -1表示没有访问过
        
        function<int(int, int, int)> dfs = [&](int i, int last, int left) -> int {
            if (i == 0) return 1; // 是一个合法结果
            if (cache[i][last][left] != -1) return cache[i][last][left];
            long long res = 0;
            for (int j = 0; j < 6; j ++) {
                if (j != last) res += dfs(i - 1, j, rollMax[j] - 1);
                else if (j == last && left > 0) res += dfs(i - 1, j, left - 1);
            }
            res %= MOD;
            cache[i][last][left] = res;
            return res;
        };

        long long res = 0;
        for (int j = 0; j < 6; j ++) {
            res += dfs(n - 1, j, rollMax[j] - 1);
        }
        res %= MOD;
        return res;
    }
};

记忆化哈希表代码:

由于unordered_map不支持元组作为key值，有以下两种方式:

自定义元组的hash函数传入
将递归入参封装成string的形式 encoder = "i last left"

hash函数发生的冲突的概率越小，程序执行效率越高，在一定程度上会影响程序运行效率

// 自定义元组的hash函数传入

typedef tuple<int, int, int> TIII;
typedef long long LL;
struct SimpleTupleHash {
    std::size_t operator()(const std::tuple<int, int, int>& p) const {
        return get<0>(p) ^ get<1>(p) ^ get<2>(p);  // => 过31个样例 
        // get<0>(p) ^ get<1>(p) & get<2>(p);      // => 过29个样例
    }
};
class Solution {
    const int MOD = 1e9 + 7;
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        unordered_map<TIII, LL, SimpleTupleHash> cache;
        
        function<int(int, int, int)> dfs = [&](int i, int last, int left) -> int {
            if (i == 0) return 1; // 是一个合法结果
            if (cache.count({i, last, left})) return cache[{i, last, left}];
            
            LL res = 0;
            for (int j = 0; j < 6; j ++) {
                if (j != last) res += dfs(i - 1, j, rollMax[j] - 1);
                else if (j == last && left > 0) res += dfs(i - 1, j, left - 1);
            }
            res %= MOD;
            cache[{i, last, left}] = res;
            return res;
        };

        LL res = 0;
        for (int j = 0; j < 6; j ++) {
            res += dfs(n - 1, j, rollMax[j] - 1);
        }
        res %= MOD;
        return res;
    }
};

// 将递归入参封装成string的形式
typedef long long LL;

class Solution {
    const int MOD = 1e9 + 7;
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        unordered_map<string, LL> cache;  // => 过29个样例
        
        function<int(int, int, int)> dfs = [&](int i, int last, int left) -> int {
            if (i == 0) return 1; // 是一个合法结果
            string encoder = to_string(i) + " " + to_string(last) + " " + to_string(left);
            if (cache.count(encoder)) return cache[encoder];
            
            LL res = 0;
            for (int j = 0; j < 6; j ++) {
                if (j != last) res += dfs(i - 1, j, rollMax[j] - 1);
                else if (j == last && left > 0) res += dfs(i - 1, j, left - 1);
            }
            res %= MOD;
            cache[encoder] = res;
            return res;
        };

        LL res = 0;
        for (int j = 0; j < 6; j ++) {
            res += dfs(n - 1, j, rollMax[j] - 1);
        }
        res %= MOD;
        return res;
    }
};

dp

1比1翻译成递推做法：

记忆化数组改为dp状态数组 $f$
递归边界改为初始值
递归入参改为循环(每有一个入参，就有一层循环)

就完事了。

状态: $f[i][j][k]$ 已经完成了 $i$ 次掷骰子，第 $i$ 次掷的数字是 $j$ ，并且已经连续掷了 $k$ 次 $j$ 的合法序列数

typedef long long LL;

class Solution {
    const int MOD = 1e9 + 7;
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        // 记忆化改dp数组
        int f[n][6][15];
        memset(f, 0, sizeof f);
        
        // 递归边界改为初始值
        for (int j = 0; j < 6; j ++) {
            for (int k = 0; k < rollMax[j]; k ++) {
                f[0][j][k] = 1;
            }
        }

        // 递归入参改为循环
        for (int i = 1; i < n; i ++) {
            for (int last = 0; last < 6; last ++) {
                for (int left = 0; left < rollMax[last]; left ++) {
                    LL res = 0;
                    for (int j = 0; j < 6; j ++) {
                        if (j != last) res += f[i - 1][j][rollMax[j] - 1];
                        else if (j == last && left > 0) res += f[i - 1][j][left - 1];
                    }
                    res %= MOD;
                    f[i][last][left] = res; 
                }
            }
        }

        LL res = 0;
        for (int j = 0; j < 6; j ++) {
            res += f[n - 1][j][rollMax[j] - 1];
            res %= MOD;
        }
        return res;
    }
};

复杂度分析

时间复杂度: $O(n m S)$ , 其中 $m$ 为 $\operatorname{rollMax}$ 的长度, 即 $6, S=\sum \operatorname{rollMax}$ , 这不会超过 $6 \times 15=90$ 。动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的转移个数。本题中状态个数等于 $O(n S)$ , 而单个状态的转移个数为 $O(m)$ , 因此时间复杂度为 $O(n m S)$ 。
空间复杂度: $O(n S)$ 。

优化

class Solution {
    const int MOD = 1e9 + 7;
public:
    int dieSimulator(int n, vector<int> &rollMax) {
        int m = rollMax.size(), f[n][m], s[n];
        for (int j = 0; j < m; ++j) f[0][j] = 1;
        s[0] = m;
        for (int i = 1; i < n; ++i) {
            s[i] = 0;
            for (int j = 0; j < m; ++j) {
                int res = s[i - 1], mx = rollMax[j];
                if (i > mx) res -= s[i - mx - 1] - f[i - mx - 1][j];
                else if (i == mx) --res;
                f[i][j] = (res % MOD + MOD) % MOD; // 防止出现负数
                s[i] = (s[i] + f[i][j]) % MOD;
            }
        }
        return s[n - 1];
    }
};

时间复杂度: $O(n m)$ , 其中 $m$ 为 $\operatorname{rollMax}$ 的长度, 即 $6$ 。
空间复杂度: $O(nm)$ 。

/*
状态表示 f[i][j][k]:
    集合: 所有从前 i 个人中选择 j 个人，且差值是 k (可能为负数, -400~400) 的所有方案的集合
    属性: D+P 最大值
状态计算:
    不选第 i 个人, f[i-1][j][k]
    选第 i 个人，  f[i-1][j-1][k-(p_i-d_i)] + (p_i+d_i)
    两个情况取一下 max 即可
*/

数据结构与算法

Algorithm Template C++

本博客所有文章均采用 CC BY-NC-SA 4.0 协议，禁止商用，转载请注明出处！

0x50动态规划-(3)-区间DP 上一篇

0x50动态规划-(1)-背包九讲下一篇