dp动态规划分类详解,python动态规划详解

　　(动态规划主题)[概率dp]

　　一般来说，概率DP找到正确的状态定义后，跃迁更容易想到。但状态必须是“可数的”，取范围整数作为数组下标。其实最好直接以问题为状态。如果问“N个人期望做XX件事的次数”，f[i]的设计状态表示I个人完成事情的期望。一般转移是递归的，即从上一个状态转移(填表)或者转移到下一个状态(刷表)。

　　有时候，期望DP要从终态转移到初态，也就是向后。如果f[i]表示我期望走f[i]步到达终点。这种状态的跃迁是一种刷表法，如图，其中p[]代表跃迁的概率，w[]代表跃迁对答案的贡献。一般来说，确定初始状态时可以使用前推，确定终止状态时可以使用后推。(来自概率DP/预期DP汇总)

　　1.期望可以分解为多个子期望的加权和，权重为子期望出现的概率，即e(AABB…)=AE(a)be(b)…1；

　　2.期望从后向前看。一般DP [n]=0，DP [0]就是答案；

　　3.求解过程，找出各种情况乘以这种情况发生的概率，总结出来；(转自概率dp研究笔记概率dp问题)

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。