算法

动态规划类似分治，同样是将原问题分解成子问题，通过求解子问题而得到原问题的解。但不同的是，动态规划是自底向上分解，并且会保存子问题的解，在需要时可直接拿过来使用，这一点是区别于分治的。通过对子问题解的保存，可以避免大量重复计算，从而提高运行效率。

1.1斐波那契数列问题 （n阶楼梯上楼问题） 当n>1时，第n项是前两项结果的和。如下图所示： 在这里插入图片描述 求F（6）时，需要频繁使用之前的结果，因此在计算较小项时，通过对其保存，可以大大提高计算速度。

动态规划解析： 状态定义： 设 dp 为一维数组，其中 dp[i]的值代表 斐波那契数列第 i 个数字 。 转移方程： dp[i + 1] = dp[i] + dp[i - 1]，即对应数列定义 f(n + 1) = f(n) + f(n - 1)； 初始状态： dp[0] = 0, dp[1] = 1 ，即初始化前两个数字； 返回值： dp[n] ，即斐波那契数列的第 n 个数字。

最大和的连续序列只有一个元素，即A[i]本身。也就是dp[i] = A[i]。 该最长子序列有多个元素，那么此时的dp[i] = dp[i-1] + A[i]。 所以取最大值即可。

原文链接：https://blog.csdn.net/qq_36721800/article/details/104378115

3.不同的二叉搜索树

二叉搜索树一旦形状确定，其内部节点的填充方法就是唯一确定的（从下方投影看，左到右依次增大），所以这题就是求不同形状的二叉搜索树数量，进而转换成左子树形状种类 * 右子树形状种类