概率是我们日常生活中随处可见的东西，但就是这么一个平常看起来平易近人的东西在遇上动态规划组合成概率$DP$的时候，就往往会让人血压升高抓耳挠腮。这篇$BLOG$，我将和你一起窥探概率$DP$的冰山一角，大致了解其解题思路和应对方法。 概率动态规划 要了解概率动态规划也就是概率$DP$，我们要先了解一下什么是概率。所谓概率就是反映随机事件出现的可能性大小的量度比如掷骰子出 $6$ 点的概率...
前段时间一位许久未见的小伙伴去做米哈游的面试题被数位动态规划裸题打倒了……为了帮助他走出阴霾也为了延续我们的动态规划系列，数位$DP$它终于来了。没有接触的同学也不要害怕，这一篇尽可能给你带来一篇保姆级的教学。 数位动态规划 数位$DP$是一种计数用的$DP$，一般就是要统计一个区间 $[l,r]$ 内满足一些条件数的个数。所谓数位 $DP$，我们从字面意思理解就是在数位上也就是十进制下...
说到进阶的动态规划，怎么能少了状态压缩动态规划（状压$DP$）呢。我们之前提到过，动态规划就和恋爱一般，一定要将自己的信息包括历史遗留问题交代清楚。但总是有问题很多信息很多的人存在的，我们状压DP就是用来解决这类问题的。 状态压缩动态规划 状压$DP$ 是动态规划的一种通过将状态压缩为整数来达到优化转移的目的的动态规划方法。在进行状压$DP$的时候，我们要把所有的压缩状态都看成是 $01...
在之前的动态规划专题BLOG中，我们已经学会了简单的线性动态规划啦。从这篇BLOG开始，我们就正式进入动态规划的进阶篇啦，作为进阶动态规划的第一篇BLOG，我们还是得一同学习一下我们的老朋友——树形动态规划。 树形动态规划 在学习树形动态规划之前，我们先要搞清楚一个问题，什么是树？根据图论课上学到的知识我们知道，连通的无圈图称为树。而树我们可以把它近似第看成一个分形结构，这是说我们的树其...
说到动态规划，就不得不提到区间动态规划这一重要分支。到现在都还记得当年还是OIER的时候第一次了解到区间动态规划时被其精妙的设计所折服的喜悦。所以现在就让我们一同学习以下区间动态规划，回顾当年的那份喜悦吧！ 区间动态规划 在之前的BLOG中，我们已经学习了动态规划的一些基本知识。那么什么是区间动态规划？和我们之前学过的线性动态规划有什么区别呢？ 区间动态规划，从名字来看就是在一段区间上进...