​ 在讨论贪心算法时，我们先了解贪心算法与动态规划之间的区别与联系，后面我们将发现可以用0、1背包问题和部分背包问题来比较贪心算法和动态规划的关系。

​ 对于许多最优化问题来说，采用动态规划来求解最优解有点大材小用了，只需要采用更简单有效的贪心算法就行了。贪心算法就是所做的每一步选择都是当前最佳的，通过局部最佳来寻求全局最佳解。就像砝码称重一样，总是优先选择大的砝码。

​ 如果我们想写一个单词查询的软件的话，我们的目的就是让查询的总时间最短，我们首先想到用之前的二叉查找树。我们可以用红黑树或者其它的平衡二叉树来保证每个单词的搜索时间。但是每个单词出现的频率一般不同，因此我们希望把频率较大的单词放在离根比较近的地方，频率较小的放在离叶子较近的地方。而且，我们所要查询的单词词库中没有，这也值得考虑。

​ 子序列：一个给定序列的子序列就是该给定序列去掉零个或者多个元素后的序列。例如：$Z={B, C, D, B}$是$X={A, B, C, B, D, A, B}$的一个子序列。注意顺序不能改变。

​ 公共子序列：既是序列$X$的子序列，又是序列$Y$的子序列。例如：$X={A, B, C, B, D, A, B}$，$Y={B, D, C, A, B, A}$,则序列 ${B, C, A}$ 是$X$和$Y$的一个公共子序列，长度为$4$；序列${B, C, B, A}$ 是$X$和$Y$的一个最长公共子序列（LCS​），长度为$4$.

​ 所谓矩阵链乘法是指当一些矩阵相乘时，如何加括号来改变乘法顺序从而来降低乘法次数。例如有三个矩阵连乘：$A_1\cdot A_2\cdot A_3$，其维数分别为：$10\times 100$，$100\times 5$，$5\times 50$. 如果按照$((A_1\cdot A_2)\cdot A_3)$来计算的话，求$(A_1\cdot A_2)$要$10\cdot 100\cdot 5=5000$次乘法，再乘以$A_3$需要$10\cdot 5\cdot 50=2500$次乘法，因此总共需要$7500$次乘法。如果按照$(A_1\cdot (A_2\cdot A_3))$来计算的话，求$(A_2\cdot A_3)$要$100\cdot 5\cdot 50=25000$次乘法，再乘以$A_1$需要$10\cdot 100\cdot 50=50000$次乘法，因此总共需要$75000$次乘法。可见，按不同的顺序计算，代价相差很大。

​ 和分治算法一样，动态规划是通过组合子问题的解而解决整个问题的。但是与分治算法不同的是，动态规划算法适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。动态规划通常用于最优化问题的求解。看一个问题是否适合采用动态规划算法，主要有两个标志：最优子结构和重叠子问题。

在fpga工程应用设计中，随处可见加法器，乘法器等等。现在将一些常用模块和心得体会先记录下来，以便日后使用。

在暑假的上一阶段，我终于完成了算法导论中有关排序算法和树结构的学习及具体的程序实践。回头想想，收获不小，由于我是学通信的，以后可能很少用得到，但是我觉得我学习到的不是算法本身，而是算法的思想。它可能在我日后的科研过程中有着深刻的影响。现在这段时间忙着opnet软件的学习，算法导论中图论的学习可能要暂时搁置了。图论想必在我们通信上应该用的比较多吧，比如什么最短路径问题，最大流问题，最小费用问题等等。因此学习图论是很有必要的。

​ 在了解红黑树之前，我们必须先了解二叉搜索树（又称二叉排序树，我在上一篇文章中有介绍），因为红黑树是一种特殊的二叉排序树：在每个节点上增加一个存储位来表示节点的颜色，因此红黑树共有五个域：color,key,lchild,rchild,p。

二叉排序树的性质：每个节点的左子树中的所有节点的关键字都小于该节点的关键值，而右子树中的所有节点的关键字都大于该节点的关键值。