LeetCode刷题笔记——迭代、递归、回溯、搜索、动态规划和贪心
2022-01-23

问题转换

使用计算机求解问题，首先将问题抽象，用数学语言描述和量化，一般可以认为输入一些变量的初始值和一些固定的参数，求解某个/某些目标变量，目标变量和输入变量有计算依赖的关系，下面对于一元或多元变量的值也称为状态

进一步地，限定问题的输入和求解的变量的值/状态的范围为计算机能够表示的范围，一般就是位数确定的整数或浮点数

再进一步地，限定为现实中有意义/合法的值/状态

问题求解

取所有合法状态的集合 [s1,s2,…,sn]

这类问题（也可以说不是问题），本身就要求遍历在问题背景下所有可能的合法状态，重点在于选择正确遍历策略，不遗漏不重复

满足 f(s) = C 的状态或状态集合

这类问题的每个状态做单独运算（映射），检查是否满足指定条件

最值 max(f(s)) 及对应状态 s

这类问题考虑所有状态之间的关系，求取某个统计量，最值是最常见的

直接求解

对于这些问题，如果本身就要求，或者没有数学方法和针对该问题的特殊解法（这需要人的智慧）

对计算机开始，通常的做法就是暴力遍历每一种情况进行检查/统计，以解决问题

计算机最擅长做重复的事情，如果算力和存储无限大，任何（有限步骤能够结束的）算法都能运行

然而现实是，两者都是有限的，不能无脑重复

需要尽可能在暴力的基础上，进行优化，减少需要计算的状态（不必计算或可以从其他状态的结果里得到）

可以作为优化依据的信息包括

  • 已知输入的某些信息，如有序、数据范围
  • 求解过程已计算的信息，如上界、下界

优化手段包括但不限于

  • 存储已计算的结果，避免重复计算
  • 舍弃某些分支（剪枝），因为可以根据上下界判断出结果不可能在该分支中
  • 改变求解顺序，如先排序或求解过程中排序（优先队列），这样能更多地达到上面提到的剪枝
间接求解

有时候，直接暴力求解一个问题的代价是我们不能承受的，也没办法找到较好的优化方法

间接求解是通过求解更小规模的问题，在多个子问题的结果上计算得到原问题的结果

这要求问题本身能够分解为子问题

实现手段

迭代

在高级语言中，表现为循环结构

在机器层面，通过指令的向上跳转，重复执行之前的莫某几个步骤

意在遍历每一个对象/状态，以获取最值或每一个结果

递归

嵌套的迭代

在高级语言中，表现为函数内部以不同参数调用自身

在机器层面，将当前上下文压入栈中，跳转到函数入口以不同的参数开始新的执行

动机

  • 子问题/规模更小的问题有同样的求解模式，求解过程封装为函数，可以复用函数代码，免去手动维护不同规模的问题变量
  • 待遍历的对象/状态并非以线性结构存储，从某个对象/状态可以转移到多个相邻的状态，借助函数调用栈结构，能暂存调用的父节点，以便访问多个相邻节点

具体方法

回到leetcode问题上来，这里做一些总结，未完待续。。

搜索

搜索是一般的通用解决方法

  • 可以找到所有可能的状态

  • 可以找到符合条件的某一个状态

广度优先搜索（BFS）

迭代实现的搜索，从一个状态扩展出若干个相邻的状态，加入队列中

如果所有状态构成不是树，而是图，即一个状态可能被发现多次，则需要去重

深度优先搜索（DFS）

以 https://leetcode-cn.com/problems/binary-tree-tilt/ 为例

通常需要使用全局变量/类成员变量维护某个目标值（最值/累计值）或者计数值（获取第k个遍历结果）

因为返回值可能需要用于判断某个条件

class Solution {
public:
    int ans = 0;
    int findTilt(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* node) {
        if (node == nullptr) return 0;
        int sumLeft = dfs(node->left);
        int sumRight = dfs(node->right);
        ans += abs(sumLeft - sumRight);
        return sumLeft + sumRight + node->val;
    } 
};

也可以将目标值设为函数的引用参数，调用子问题时，子问题都修改最顶层调用传入的参数，避免使用全局变量

class Solution {
public:
    int findTilt(TreeNode *root) {
        int answer = 0;
        dfs(root, answer);
        return answer;
    }
    int dfs(TreeNode *root, int &answer) {
        if (!root) return 0;
        int ls = dfs(root->left, answer);
        int rs = dfs(root->right, answer);
        answer += abs(ls - rs);
        return ls + rs + root->val;
    }
};

当然也可以使用结构体（或pair<>）组合多个返回值，避免使用全局变量

class Solution {
public:
    struct RET {
        int sum;
        int acc_tilt;
    };
    RET dfs(TreeNode* root) {
        if (root == nullptr) return {0, 0};
        RET l = dfs(root->left);
        RET r = dfs(root->right);
        return {root->val + l.sum + r.sum, abs(l.sum - r.sum) + l.acc_tilt + r.acc_tilt};
    }
    int findTilt(TreeNode* root) {
        RET res = dfs(root);
        return res.acc_tilt;
    }
}

对于需要构造所有状态的问题，通常就使用全局变量（列表）或引用参数，完成一个状态构造时加入，这种情况更偏向于回溯

使用全局变量的内存消耗通常大于引用参数，参考这个提交记录，内存分布明显有最前面两个峰，最后面还有一个峰是递归调用层数更多的方法，内存消耗也更多

启发式搜索
算法参考 [Wikipedia - A* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm) 或 [oi-wiki - A*](https://oi-wiki.org/search/astar/)。

在 算法中，我们需要使用四个距离函数 ，其中 是可以求出的，而 是无法求出的，我们需要用 近似 。设起点为 ，终点为 ，这些距离函数的意义如下：

  • 表示从起点 到节点 的「实际」路径长度，注意 并不一定是最短的；
  • 表示从节点 到终点 的「估计」最短路径长度，称为**启发函数**；
  • 表示从节点 到终点 的「实际」最短路径长度，这是我们在广度优先搜索的过程中无法求出的，我们需要用 近似 ；
  • 满足 ，即为从起点 到终点 的「估计」路径长度。我们总是挑选出最小的 对应的 进行搜索，因此 算法需要借助**优先队列**来实现。

如果读者熟悉求解最短路的 算法，就可以发现 算法是 算法在 时的特殊情况。

算法具有两个性质：

  • 如果对于任意的节点 ， 恒成立，即我们「估计」出的从节点 到终点 的最短路径长度总是不超过「实际」的最短路径长度，那么称启发函数 是可接纳的（admissible heuristic）。在这种情况下， 算法一定能找到最短路，但同一节点可能需要加入优先队列并搜索多次，即当我们从优先队列中取出节点 时， 并不一定等于从起点到节点 的「实际」最短路径的长度；

  • 如果对于任意的两个节点 和 ，并且 到 有一条长度为 的有向边， 恒成立，并且 ，那么称启发函数 是一致的（consistent heuristic）。可以证明，一致的启发函数一定也是可接纳的。在这种情况下，同一节点只会被加入优先队列一次，并搜索不超过一次，即当我们从优先队列中取出节点 时， 一定等于从起点到节点 的「实际」最短路径的长度。

回溯

DFS的一种特殊情况，参见这篇文章

使用回溯求解的问题常常原地构建和修改状态，这就要求要求能够使状态逆序恢复

在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点状态]。

回溯法的核心就是回溯，具有进入与返回顺序对称的特性，通常用来生成或查找多维的问题

可以认为状态 = (变量1，变量2，...，变量n)

回溯相当于可变重数的for循环，充分利用函数调用栈暂存信息，并且自动帮助我们恢复状态，参考下面的例子

for(val1 in 变量1)
    for(val2 in 变量2)
        ...
        for(valn in 变量n)
            check f(状态)=f(val1，val2，...，valn)

可以逐步构建状态，减少状态构建时的开销，特别是构建是依赖于前面变量的操作，

最简单的：累加

f(i, val) {
    val+=v[i];
    f(i+1, val);
    // val-=v[i]; //由于调用栈自动清理变量，省略了此步
}
// 如果是for循环（假设只在最内循环编写代码），则需要每次对所有层的val进行从头累加

复杂一些的：比如枚举状态本身，表示为一个数组，需要逐步构建数组

这种情况常常通过传引用，原地修改同一个对象，而不是拷贝构造一个新的对象

f(i, arr) {
    arr.push(i);
    f(i+1, arr);
    arr.pop(i); //回溯
}

回溯过程中可以剪枝，提前return（相当于在某个for中break），特别是一些状态之间相互耦合的情况

  • 使用变量有代价g(变量)，可在回溯过程中根据代价上限提前返回
常见的用回溯求解的问题

排列，每个元素只能用一次，需要查询某个元素是否已使用

组合/子集

  • 组合类的去重，一般通过排序后，判断选中的相邻两个数是否相同

动态规划

不同于一般的搜索，动态规划和贪心，更侧重于间接求解问题，即问题可以分解为子问题

动态规划是一种思想，对于求解的问题，其结果依赖于于重叠的子问题（否则应该使用分治，在多个机器核心上同时求解），并且每个子问题的求解顺序不影响更大的问题的结果（无后效性）

以动态规划求解问题，一般需要一个一维或多维数组，每个维度是问题的某个规模参数从，通过已知或易知的边界条件（规模最小的问题），一定的次序逐步求解较大规模的问题

140. 单词拆分 II

看看官方题解，思考一下我的做法与记忆化搜索的关系?*

300. 最长递增子序列

思考解法二：贪心+二分

410. 分割数组的最大值

思考解法二：贪心+二分

968. 监控二叉树

思考这题我的做法是贪心吗？贪心为什么可行

376. 摆动序列

思考这题，类似最长递增子序列的O(n^2)的动态规划为什么本题能优化到O(n)，和O(n)的贪心是什么区别

记忆化搜索

记忆化搜索和动态规划在本质上是一样的，复用重叠子问题，相同的子问题只求解一次

动态规划由迭代实现，由于更大规模的问题依赖于规模小的问题，因此求解顺序上有一定的要求

  • 有时候数据的分布顺序不是实现正确求解的顺序，所依赖的子问题可能尚未求解或尚不能正确求解（因为更小的子问题尚未求解）
  • 比如，329. 矩阵中的最长递增路径，如果想要迭代求解，必须先对所有坐标按对应值排序或拓扑排序，依照此顺序求解
  • 分糖果那题似乎也可以拓扑排序+动态规划

记忆化搜索由函数递归实现，并不以特定的顺序求解，

  • 每当遇到一个问题，分解为若干个子问题
  • 如果子问题已经求解过（记忆在存储中），则直接使用结果；
  • 如果子问题未求解，则递归地求解子问题，并记录在存储中

贪心

搜索
背景设置