LUO

贴一个自顶向下带个备忘录C++ ```C++ bool dp(vector& nums, int i, int size) { // base case int j = size; if (size == 0) return true; // 背包被装满了，返回true if (i == -1) return...

东哥，请问自顶向下的DP如何对备忘录进行空间压缩呢？

贴一个C++版本，用了两个哈希链表，感觉比较容易理解和记住 ```C++ struct Node { int key; int val; int freq; Node(int _key, int _val, int _freq): key(_key), val(_val), freq(_freq) {} }; class LFUCache { unordered_map key_table; // 每个键key保存着对应的链表节点的地址，注意这里必须保存地址，否则对链表节点的修改需要手动更新哈希表 unordered_map...

确实看懂了 也能自己写出来，但是这种思路真的很巧妙，感觉没做过的话面试应该在有限时间内想不出来的。 感觉j可以从3开始一直到i，毕竟如果j = 2实际就是屏幕上没有A就ctrlA ctrlC，相当于什么也没复制

C++贴一个精简版本的DP数组 ```C++ class Solution { vector dp_table; // 记录在每一个位置[i, j]的下降最小路径和 public: int minFallingPathSum(vector& matrix) { int n = matrix.size(); dp_table.resize(n, vector (n, INT_MAX)); for (int i = 0; i <...

贴一个C++双百版本，并且带for循环便于理解。实际上这里的for循环是可以省略的，因为同一个位置上只有两种情况: 左括号和右括号。前面带for循环是因为同一个位置的情况有k种，这里可以直接手写出来所以就省略for了 ```C++ class Solution { vector res; vector dir {'(', ')'}; public: void backtrack(int n, int left, int right, string& onPath) { // 放n个括号，代表左括号有n个，右括号也有n个，这样才合法。并且在每个位置i时，[0, i]中左括号的总数一定大于右括号的数量 if (left < 0...

> 东哥，这篇文章的动态规划用的解法里，base case和之前一篇文章的感觉有点出入，让我迷茫了。这篇的base case是dp[0][..] = 0， dp[..][0] = 0, 唯独dp[0][0]=1，但是之前的完全背包问题是dp[0][..] = 0， dp[..][0] = 1。现在有点迷糊 前面的完全背包问题是硬币币种的选择，硬币的面额不可能存在0; 分割子集那道题对应的也是集合中全部都是正整数，因此可以用dp[...][0]概括所有base case，这里数组中出现的元素可能等于0，因此没法统一概括了只有dp[0][0]可以为1

贴一个直接DP法，由于j可能为负所以没法用数组保存，因此存在重复子问题计算，但C++依然能通过 ```C++ class Solution { public: // 返回从1到i个数中，目标和为j的组合数目 int dp(vector& nums, int i, int j) { if (i == -1) { if (j == 0) return 1; return 0; }...

> @lhcezx 👍，其实这种情况也是可以用备忘录的，python 可以把元组 `(i, j)` 存到备忘录 dict 中 ，cpp 的话可以把字符串 `string key = i + "," + j` 作为 `unordered_map` 备忘录中的键。 @labuladong 感谢东哥回复，补充一下带备忘录版 ```C++ class Solution { unordered_map memo;...

东哥我没理解非满二叉树子树的递归复杂度计算。对于满二叉树的子树遍历中有两个while，按照层数从上到下高度为log(n)因此复杂度为O(logn)没毛病，非满二叉树的子树相当于需要遍历该子树中的每一个节点吧？感觉递归次数并不是树的高度而是子树中节点的数目，递归函数每次执行的复杂度为O(logn)，节点数目准确来说应该是N / 2 (因为子树包含一半的节点)， 因此复杂度不应该是O(logn * n / 2)嘛？ 如果我说的不对麻烦大佬指正，没太明白怎么计算出的log^2(n)