递归

思路

某个函数直接或者间接地调用自己，把原问题的求解转换为许多性质相同但是规模更小的子问题。

重点关注如何把原问题划分成符合条件的子问题，以及最简问题的求解。

套路

int func(问题规模) {
  if (终止条件) {
    return 最小子问题解;
  }
  return func(缩小规模);
}

问题规模通常包含数据和其当前状态

优化

所谓的剪枝，即提前判断当前状态是否有必要继续分解下去而提前结束

备忘录

int memo[MAX]
int func(问题规模) {
  if (memo[当前状态]) {
    return 当前问题解
  }

  if (终止条件) {
    return 最小子问题解;
  }
  return func(缩小规模);
}

1. 定义备忘录，记录问题状态和其对应的解
2. 判断当前状态是否在备忘录中，提前返回解（有解和无解）

最优化

int ans；//当前最差状态
int func(问题规模) {
  if (当前状态 比 ans 更差) {
    return 无解
  }

  if (终止条件) {
    return 最小子问题解;
  }
  return func(缩小规模);
}

1. 定义临时状态，记录当前最差状态
2. 判断当前状态是否比最差状态还差或者直接不可用，提前返回解（无解）

示例

力扣1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

标准套路：

class Solution:
    def tribonacci(self, n: int) -> int:
        if n < 2:
            return n
        elif n == 2:
            return 1
        else:
            return self.tribonacci(n - 3) + self.tribonacci(n - 2) + self.tribonacci(n - 1)

时间复杂度3N，容易运行超时

tribonacci(k)被运行多次

备忘录优化：

class Solution:
    def tribonacci(self, n: int) -> int:
        if n <= 2:
            return 1 if n else 0

        memo = [-1] * (n + 1)
        memo[0] = 0
        memo[1] = 1
        memo[2] = 1

        return self.trib(n, memo)

    def trib(self, n: int, memo: List):
        if memo[n] != -1:
            return memo[n]
        else:
            memo[n] = self.trib(n - 3, memo) + self.trib(n - 2, memo) + self.trib(n - 1, memo)
            return memo[n]

memo做备忘录，边执行边记录解，重复运算直接查找备忘录

memo可以提前求所有解，也可以边计算边动态记录解