囚徒的困境

突然发现一门很有意思的课程,在算法竞赛中也是一个十分有意思的分支。不过在算法中,博弈论一般都假定博弈的参与者都会做出最优的选择,且处于平等博弈。当然还有非零和博弈啊。
可能更新的一系列的博弈论的知识,会结合相关的背景以及例子,讲解后面蕴含的博弈知识。

dp优化--连续递推的时间和空间优化

复习到k阶fibonacci数的时候,老师讲这是比较难的,然而不就是dp优化吗。
通过化简合并式子减少时间复杂度。
通过对前面无用的状态的覆盖来减少空间复杂度。(若要查询任意小于等于m的k阶fibonacci数这样的覆盖是不行的,必须全部记录下来。同01背包的一维的滚动数组。)
顺便复习一下模板计数dp.

状压dp

状态压缩:将集合的状态用一个数字表示,这个数字的每一位是0或者1,表示着一个元素的两种状态。
此处应该介绍一下位运算和性质(脑补一下?)
几大类状压dp:

  • TSP问题
  • 密铺问题(轮廓线法)
  • 插头dp
  • 传统的状压dp问题
    后面的两类问题并不会。
{{ live2d() }}