初始化 base case

@liwei

Plan

  • fucking algorithm
    • dynamic programming
    • backtracking

Notes

这段时间，每天忙忙碌碌，以工作忙作为自己偷懒的接口。梦中惊醒，竟发现上次happy time已经是接近两月之前。遥想疫情期间，壮志凌云，给自己定下来的目标是管理技术两不误，成为既能带领团队，又能独当一面的全能型人才。如今回首，羞愧不已。趁着周末得闲，看到github上的一个系列文章fucking-algorithm，作者思路的清晰和总结能力，细细读来，佩服至极，惊为天人。这个系列文章对现在的我来说，仿佛当年高中的我，读到了五年高考三年模拟。因此，今天重新捡起happy time，只希望能保持对技术的敬畏，不忘初心，砥砺前行。

动态规划 cheet sheet

动态规划算法，一般用于求解最值，其核心思想其实是穷举。与一般穷举问题不同在于，其存在重叠子问题，并且一定具备最优子结构。参考算法导论等经典书籍，求解动态规划算法最重要的一点是写出状态转移方程。写出状态转移方程的思考框架为：

base case -> 定义“状态” -> 定义“选择” -> 定义dp函数/数组的含义。

其完整的算法框架为：

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

只要按照上面的框架进行思考，无往不利。典型的问题可以参考“322. 零钱兑换”。

回溯 Backtrack

解决回溯问题，实际上是一个决策树的遍历过程。需要思考的问题是三个：

  1. 路径：已经做过的决策
  2. 选择列表：当前可以做的决策
  3. 结束条件：无法再做选择的状态

完整的算法框架为：

init result = []

def backtrack(路径，选择列表):
    if 满足条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径， 选择列表)
        撤销选择

上面算法核心为for循环，递归之前做选择，递归之后撤掉选择，尝试其他选择。

More

NULL