算法设计与分析Ch06

弃坑了，转战Jeff的《Algorithms》

第六章 动态规划算法的典型应用

图像压缩

如果大片面积为同一颜色，则要如何压缩？

变位压缩

子问题

伪代码

小结

• 图像变位存储问题的建模
• 子问题边界的界定
• 递推方程及初值
• 伪码
• 标记函数与解的追踪
• 时间复杂度

最大子段和

问题介绍

算法

动态规划

子问题

伪代码

小结

• 三个算法: 暴力，分治，动态规划
• 动态归划算法:
  • 子问题界定
  • 列优化函数的递推方程和边界条件（不一定是原问题的优化函数）
  • 自底向上计算，设计备忘录（表格）
  • 如何根据动态规划的解找原问题的解
  • 时间复杂度估计

最优二叉检索树

概念与检索方法

数据元素存取概率分布

问题

子问题

小结

RNA 二级结构预测

问题

目标：由一级结构来预测二级结构

建模

小结

• 划分子问题，确定子问题边界 $i,j$ 与归约方法。
• 定义优化函数，列递推方程和初值。
• 自底向上计算，设计备忘录 (表格)
• 设立标记函数，记下最优划分位置
• 时间复杂度估计

序列比对

问题

子问题

动态规划算法设计要点

（然后就弃坑了，筹备算法研讨班ing）