分治

精髓所在

分治，分而治之。

算法简介

分治，又称记忆化搜索（注意这里跟普通的搜索有着很大的区别），是一种通过记录已经求解过的状态信息，从而避免求解重复或无用状态的一种算法，也是一种常见的动态规划实现方式（其他的比如递推等）。

例题

斐波那契数列

给定 \(n\)，求斐波那契数列的第 \(n\) 项。

从结果 \(f(n)\) 出发，我们知道 \(f(i)=f(i-1)+f(i-2)\)，那么我们只需要照着这个式子进行推导就行了，时间复杂度 \(\mathcal O(2^n)\)。

是什么导致了如此高的复杂度呢？其实就是因为同一个 \(f(i)\) 会求解多次，而其实他们的值是固定的，因此我们就使用一个数组，存下 \(f(i)\)，这样子就可以在需要重复调用的时候直接调用之前的解，达到了“记忆化”的效果。

这种方法每一个状态只会访问一次，而状态的数量有 \(n\) 个，这种算法的时间复杂度就降到了 \(\mathcal O(n)\)。

代码

C++Java

int solve(int x) {
  if (x <= 2) {
    return 1;
  }
  if (f[x]) {
    return f[x];
  }
  return f[x] = solve(x - 1) + solve(x - 2);
}

public class Main {
  public static int solve(int x) {
    if (x <= 2) {
      return 1;
    }
    if (f[x]) {
      return f[x];
    }
    f[x] = solve(x - 1) + solve(x - 2);
    return f[x];
  }
}

注意

分治需要从结束状态开始，然后不断向前遍历，最后往后回滚。这种思路是反向的，只有这样子才能保证记忆化数组的最优。

如何写分治

如何写出一个完美的分治？

• 把状态和转移方程列出来，然后照着建模、写出 dfs 函数；
• 首先写一个从结束状态开始的 dfs，然后加上记忆化。

评论