概述: 1.动态规划是通过组合子问题的解而解决原问题的。 2.动态规划适用于子问题不是独立的情况,也就是各子问题的包含公共的子子问题。 3.动态规划对每个子问题只求解一次,将其结果保存在一张表中。 4.动态规划的设计步骤:a.描述最优解的结构b.递归定义最优解的值c.按自底向上的方式计算最优觖的值d.由计算出的结构构造一个最优解 15.1钢条切割 钢条切割问题:给定定长的钢条和价格表,求切割方案,使得收益最大。如果n英寸的钢条的价格足够大,则不需要切割。 代码如下: //朴素递归求解钢条切割收益,由于递归过程中反复…

2014年8月18日 0条评论 2点热度 阅读全文

12.1 二叉查找树 定义:设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点,则key[y]≤key[x]。如果y是x的右子树中的一个结点,则key[x]≤key[y]. 前序遍历:先遍历根再遍历左右子树,简称根-左-右。 中序遍历:先遍历左子树再遍历根再遍历右子树,简称左-根-右。 后序遍历:先遍历左右子树再遍历根,简称左-右-根。 书中中序遍历代码: //中序遍历 void INORDER-TREE-WALK(struct Tree *p) { if (p->key) { INORDER-TR…

2014年6月6日 0条评论 2点热度 阅读全文

查找树是一种数据结构,它支持多种动态集合操作,包括search, minimum, maximum, predecessor, successor, insert以及delete。他既可以用作字典,也可以用作优先队列。 二叉查找树上基本操作的执行时间和树的高度成正比。对一棵n个结点的完全二叉树来说,这些操作的最坏情况运行时间为Θ(lgn)。但是如果树是含有那个结点的线性链,则这些操作的最坏运行时间是Θ(n)。本章可以看到一棵随机构造的二叉查找树的期望高度为O(lgn)。 实际中,并不能总是保证二叉查找树是随机构造的…

2011年2月26日 0条评论 6点热度 阅读全文