因为最近一段时间接触了一些Leetcode上的题目，发现许多题目的解题思路相似，从中其实可以了解某类算法的一些应用场景。
这个随笔系列就是我尝试的分析总结，希望也能给大家一些启发。
一言以蔽之，动态规划就是将大问题分成小问题，以迭代的方式求解。
可以使用动态规划求解的问题一般有如下的两个特征：
1、有最优子结构（optimal substructure）
即待解决问题的最优解能够通过求解子问题的最优解得到。
2、子问题间有重叠（overlapping subproplems）
即同样的子问题在求解过程中会被多次调用，而不是在求解过程中不断产生新的子问题。动态规划一般会将子问题的解暂时存放在一个表中，以方便调用。（这也是动态规划与分治法之间的区别）
下图是斐波那契数列求解的结构图，它并非是“树状”，也就是说明其子问题有重叠。
1、分析得到结果的过程，发现子问题（子状态）；
2、确定状态转移方程，即小的子问题与稍大一些的子问题间是如何转化的。
以斐波那契为例（两种方式：自顶向下与自底向上）以求解斐波那契数列为例，我们很容易得到求解第N项的值的子问题是第i项（i＜N）的值。
而状态转移方程也显而易见：f(n) = f(n-1) + f(n-2)
由此我们可以得到相应迭代算法表达：
function fib() if n <= 1 return n return fib(n - 1) + fib(n - 2)不过，如之前所说，动态规划一个特点就是会存储子问题的结果以避免重复计算，（我们将这种方式称作memoization）通过这种方式，可以使时间复杂度减小为O(N)，不过空间复杂度因此也为O(N)。我们可以使用一个映射表（map）存储子问题的解:
var m := map(0 -> 0, 1 -> 1) function fib(n) if key n is not in map m m[n] := fib(n - 1) + fib(n - 2) return m[n]上面的方式是自顶向下（Top-down）方式的，因为我们先将大问题“分为”子问题，再求解/存值；
而在自底向上（Bottom-up）方式中，我们先求解子问题，再在子问题的基础上搭建出较大的问题。（或者，可以视为“迭代”(iterative)求解）通过这种方法的空间复杂度为O(1)，而并非自顶向下方式的O(N)，因为采用这种方式不需要额外的存值。
分治法（Divide and Conquer）的思想是：将大问题分成若干小问题，每个小问题之间没有关系，再递归的求解每个小问题，比如排序算法中的“归并排序”和“快速排序”；
而动态规划中的不同子问题存在一定联系，会有重叠的子问题。因此动态规划中已求解的子问题会被保存起来，避免重复求解。
动态规划与贪心算法贪心算法（greedy algorithm）无需求解所有的子问题，其目标是寻找到局部的最优解，并希望可以通过“每一步的最优”得到整体的最优解。
如果把问题的求解看作一个树状结构，动态规划会考虑到树中的每一个节点，是可回溯的；而贪心算法只能在每一步的层面上做出最优判断，“一条路走到黑”，是“一维”的。因此贪心算法可以看作是动态规划的一个特例。
那么有没有“一条路走到黑”，最后的结果也是最优解的呢？
当然有，比如求解图的单源最短路径用到的Dijkstra算法就是“贪心”的：每一次都选择最短的路径加入集合。而最后得到的结果也是最优的。（这和路径问题的特殊性质也有关系，因为如果路径的权值非零，很容易就能得到路径递归的结果“单增”）
96. Unique Binary Search Trees
Given n, how many structurally unique **BST**'s (binary search trees) that store values 1 ... n?
给定n，求节点数为n的排序二叉树（BST）共有几种（无重复节点）。
可以令根节点依次为节点1~n，比根节点小的组成左枝，比根节点大的组成右枝。
子树亦可根据此方法向下分枝。递归求解。
令G(n)为长度为n的不同排序树的数目（即目标函数）；
令F(i,n)为当根节点为节点i时，长度n的不同排序树的数目。