1、程序设计实习习题课枚举 枚举 :在条件范围内对相关变量依次取值，列出所有可能的情况，逐一检查是否是问题的解 关键： 有序地枚举解空间，不漏掉情况 尽早发现不是解的情况 枚举中的优化搜索：复杂的、高级的枚举 搜索 : 解空间的每个元素是一个动作的序列 F 将初态 S0变换为另一个状态 F(S0) 如果 F(S0)是符合要求的 S*, 那么 F是真解 , 否则是伪解 按照一定规则 , 确定在每个状态 S下 ,分别有哪些动作可供选择 深度优先搜索，广度优先搜索 需要对遍历过的状态进行标记 采用 递归 的办法 , 产生每个动作序列 递归的出口：达到目标状态；状态已经遍历过递归 递归 : 从目标出发，把
2、一个问题逐级分解成子问题 子问题与原问题之间是纵向的、同类的关系 语法形式上：在一个函数的运行过程中，调用这个函数自己 直接调用：在 fun()中直接执行 fun() 间接调用：在 fun1()中执行 fun2()；在 fun2()中又执行 fun1() 关键： 递推关系 终止条件 递归算法思路清晰，程序易读易写动态规划 动态规划：采用自底向上的递推算法 从已知条件出发，将计算出的结果保存起来，直接用于后续计算。 避免树形递归的大量重复运算。 同样需要寻找递推关系小结 根据题意，以及自己对方法的熟悉程度，灵活选择各种方法，综合使用 直接解决 枚举，（搜索） 递归，转化为规模更小的同类问题 遇到
3、具有多阶段过程的问题，先走一步试试，考虑如何将问题转化（如考虑第一步或最后一步） 难的不会想简单的poj 2766 最大子矩阵 题目描述已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空 (大小至少是 1 * 1)子矩阵。 比如，如下 4 * 4的矩阵：0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2其最大子矩阵是：9 2-4 1-1 8这个子矩阵的大小是 15。poj 2766 最大子矩阵 输入输入是一个 N * N的矩阵。输入的第一行给出 N (0 N = 100)。再后面的若干行中，依次（首先从左到右给出第一行的 N个整数，再从左到右给出第二行的 N个整数 ）给出矩阵中的 N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在 -127, 127。 输出输出最大子矩阵的大小。poj 2766 最大子矩阵 样例输入4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 样例输出15 枚举：依次计算每个子矩阵的值。i、 j分别为子矩阵的纵坐标。 i=0时：0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2bN:存放子矩阵每列的和则问题转换为寻找 bN的最大子序列。解题思路
