动态规划
📚 动态规划
动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构）
- 共性：找到重复子问题
- 差异性：最优子结构、中途可以淘汰次优解
💻 代码模板
- 一维路径
斐波那契数列：通过递归，先计算 f(0), f(1), f(2)，然后计算 f(3), f(4)，依次类推，直到计算出 f(n)。
1 | f(n) = f(n-1) + f(n-2) |
- 二维路径
从左上角走到右下角，每次只能向右或向下走，问有多少种走法。
走到 f(m, n)，只能从 f(m-1, n)或 f(m, n-1)走过来。
1 | f(i, j) = f(i+1, j) + f(i, j+1) |