dynamic programming

本质 ： 记忆化搜索
避免重复计算

多重循环vs记忆化搜索
多重循环：可以不用递归 可以对空间复杂度进行优化

步骤：初始化，循环，终点

什么情况下使用动态规划？

  1. 求最大最小值、最优值
  2. 判断是否可行
  3. 统计方案个数

什么情况下不会使用动态规划？

  1. 求出所有 具体 的方案 而非方案个数
  2. 输入数据是一个集合 而不是一个序列 跟顺序无关
  3. 暴力算法的复杂度已经是多项式级别
    动态规划擅长优化指数级别到多项式复杂度
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容