美文网首页
动态规划 我的体会

动态规划 我的体会

作者: 冷殇弦 | 来源:发表于2017-09-29 07:58 被阅读0次

Dynamic Programming是刷Leetcode当中很重要的一道关卡。阅读了知乎以及一些科技blog之后对于动态规划还是一知半解。终于自己刷了几道题之后有了一些体会,所以记录在此。不敢说专业准确,只是“纸上得来终觉浅,觉知此事要躬行”

DP适用题目

DP 适用题目对我来说有两个特征:

  1. 有子问题:不管是用递归还是循环,最终求解问题都应该能被拆解成求解子问题,in other words,可以得出状态递推方程。
  2. 有“讨价还价”的过程:也可以说成是有重叠状态,需要剪枝。例如1,3,5硬币求得10等的问题,以及类似的0-1背包问题,都涉及到重叠状态,用brutal force 或者greedy会有重叠或者次优解优先于最优解的情况。所以,面对这种需要

相关文章

  • 动态规划 我的体会

    Dynamic Programming是刷Leetcode当中很重要的一道关卡。阅读了知乎以及一些科技blog之后...

  • Algorithm进阶计划 -- 动态规划(上)

    动态规划动态规划的基本原理动态规划的运用 1. 动态规划的基本原理 动态规划(Dynamic Programmi...

  • 动态规划 Dynamic Programming

    从运筹学和算法的角度综合介绍动态规划 算法分类总结动态规划与静态规划的关系浅析静态规划和动态规划动态规划解非线性规...

  • 算法3:动态规划

    5.动态规划5.1 什么是动态规划?5.2 自底向上的动态规划:5.3 自顶向下的动态规划5.4 0-1背包问题:...

  • 4. 动态规划算法

    1. 动态规划算法总结2. 漫画:什么是动态规划?3.算法之动态规划4. 动态规划-算法

  • Dynamic Programming(动态规划)类算法分析随笔

    #动态规划 关于动态规划,先摘一段[wiki][1]的描述: ``` 动态规划(英语:Dynamic progra...

  • 什么是动态规划

    目录 动态规划解决了什么 什么是动态规划 典型的动态规划 1. 动态规划解决了什么 的思想就是将大问题拆分成小问题...

  • 《数据结构与算法之美》27——初识动态规划

    前言 今天开始学习动态规划,一共有三节,分别是:初识动态规划、动态规划理论、动态规划实战。今天这一节就是初识动态规...

  • 如何解决动态规划问题

    曾经的我以为动态规划很神秘,很难理解。后来随着刷的动态规划相关的题越来越多,对于动态规划也就驾轻就熟了。我一开始来...

  • LeetCode基础算法-动态规划

    LeetCode基础算法-动态规划 LeetCode 动态规划 动态规划的核心步骤: 查看大问题的最优解能否使用小...

网友评论

      本文标题:动态规划 我的体会

      本文链接:https://www.haomeiwen.com/subject/iumbextx.html