2设计动态规划算法的主要步骤为：
（1）找出最优解的性质，并刻划其结构特征。

（2）递归地定义最优值。

（3）以自底向上的方式计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

3. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。

而用分治法求解的问题，经分解得到的子问题往往是互相独立的。

贪心选择算法与动态规划算法的异同点：同：都要求问题具有最优子结构性质；异：动态规划算法为自底向上的方式解各子问题，贪心算法为自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择问题就转换为规模更小的字问题。

6. 分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决；
（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;
（3）利用该问题分解出的子问题的解可以合并为该问题的解；
（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

P：也即是多项式复杂程度的问题。

NP就是多项式复杂程度的非确定性问题。

NPC(NP Complete)问题
ADT 抽象数据类型
分析问题→设计算法→编写程序→上机运行和测试
算法特性1. 确定性、可实现性、输入、输出、有穷性
算法分析目的2. 分析算法占用计算机资源的
情况，对算法做出比较和评价，设计出额更好
的算法。

3. 算法的时间复杂性与问题的规模相关，是
问题大小n的函数。

算法的渐进时间复杂性的含义：当问题的规模
n趋向无穷大时，影响算法效率的重要因素是
T(n)的数量级，而其他因素仅是使时间复杂度
相差常数倍，因此可以用T(n)的数量级(阶)
评价算法。

时间复杂度T(n)的数量级(阶)称为
渐进时间复杂性。

最坏情况下的时间复杂性和平均时间复杂性有什么不同？
最坏情况下的时间复杂性和平均时间复杂性
考察的是n固定时，不同输入实例下的算法所
耗时间。

最坏情况下的时间复杂性取的输入实
例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn
平均时间复杂性是所有输入实例的处理时间
与各自概率的乘积和：
A(n) =∑P(I)T(n，I) I∈Dn
为什么要分析最坏情况下的算法时间复杂
性？最坏情况下的时间复杂性决定算法的优
劣，并且最坏情况下的时间复杂性较平均时间
复杂性游可操作性。

1.贪心算法的基本思想？
是一种依据最优化量度依次选择输入的分级处理方法。

基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。

如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

贪心选择算法与动态规划算法的异同点：同：都要求问题具有最优子结构性质；异：动态规划算法为自底向上的方式解各子问题，贪心算法为自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择问题就转换为规模更小的字问题。