tags： DP 笔记
updata：总结了部分期望内容
学长疯狂拉进度系列
动态规划算法（\(DP,Dynamic\) \(programming\)），它针对满足某一条件的一类问题，对各状态维度进行分阶段、有顺序、无重复、决策性地转移求解。
能干什么？动态规划通过把复杂问题分解为相对简单的子问题的方式来求解原问题。
动态规划三要素分别是状态、决策、阶段。
动态规划三条件分别是子问题重叠、无后效性、最优子结构。
解题步骤
确定问题的研究对象，即确定状态。划分阶段，确定阶段之间的状态转移方程。考察此问题现在可否用动态规划来解决：考察此问题是否具有最优子结构。考察此问题是否为无后效性。如果发现此问题目前不能用动态规划来解决，则应该调整相应的定义与划分，以达到可以用动态规划来解决。\(PS\)：不需要知道太多概念，能拿来用就行了。
定义样本（\(\omega\)）：一次随机试验产生的一个结果。样本空间（\(\Omega\)）：一个随机试验的所有可能的结果的全体，即\(\Omega=\{\omega\}\)。事件（\(A\)）：某一类结果，即\(A\subset\Omega\)。基本事件（\(s\)）：各个互斥的事件即为基本事件。我们借助样本空间S来定义概率。样本空间是基本事件的集合。
概率论公理 样本空间\(S\)的概率分布\(Pr\{\}\)是一个从\(S\)的事件到实数的映射，它满足以下公理： 非负性：对于任意事件\(A\)，\(Pr\{A\}\geqslant 0\)。正则性：\(Pr\{S\}=1\)。可列可加性：对于两个互斥事件\(A\)与\(B\)，有\(Pr\{A\cup B\}=Pr\{A\}+Pr\{B\}\)。更一般地，对于任意有限或无限事件序列\(A_1,A_2,...,\)若其两两互斥，则有：\[ Pr\{\bigcup_iA_i\}=\sum Pr\{A_i\} \]期望简单理解，期望的意义就是概率的加权平均数。
假设某随机试验\(X\)共有\(n\)种互斥的事件可能发生，其中第\(i\)个事件发生的概率为\(P_i\)，价值为\(X_i\)，则这个随机试验的期望是\(E(X)=\sum P_iX_i\)。
期望也可以从频率的角度来理解，我们知道如果不断重复某个随机试验，某个事件发生的频率会趋近于其概率，而将发生过所有事件的价值取平均值，这个值就会趋近于这个随机试验的期望。
\[ E(X+Y)=E(X)+E(Y)....(1) \]
\[ E(aX)=aE(X)..............(2) \]
\[ E(XY)=E(X)E(Y)..........(3) \]
证明如下
(1)式:
(2)式:
(3)式:
用数学归纳法可推广到多个。
所求结果为某事件的期望的动态规划。
实际上这类动态规划并不是一个新的类型，它都是在原有的动态规划的基础上，将所求的值改成了概率和期望的相关值，换句话说，这类问题的难度其实还是在动态规划的原型上，概率和期望只是表象。
现在大多数期望题就是手动找公式或者\(DP\)推出即可，只要处理好边界，然后写好方程，就行了。与常规的求解不同，数学期望经常逆向推出，但不全是。它的代码量很短，但思维难度明显较高。
比如数学期望的\(f[x]\)一般表示到了\(x\)这一状态还差多少，最后答案是\(f[0]\)。
总之，该推公式的还是推，该在图上跑的还是在图上跑，只是注意状态的设计。
入门：
过河：有个人每天要去公司上班，每次会经过\(n\)条河，家和公司的距离为\(d\)，默认在陆地的速度为\(1\)， 给出\(n\)条河的信息，包括起始坐标\(p\)，宽度\(L\)，以及船的速度\(v\)。船会往返在河的两岸，人到达河岸时， 船的位置是随机的（往返中）。求人达到公司所需要的期望时间。最坏情况下，过一条河需要\(3*L/v\)的时间；最好的情况下，过一条河需要\(L/v\)的时间，又因为船的位置随机，所以过河时间线性分布，于是期望取个平均值\(2*L/v\)就行了。
掷骰子：一个\(n\)面的骰子，求期望掷几次能使得每一面都被掷到。考虑集合中选取一个不同于已选的新数的概率，所以可以设计\(DP\)方程：\(f[i]\)表示取了\(i\)种数后还需取的期望值。
取了\(i\)种数，当前取的是新数的概率是\(\frac{n-i}{n}\)，当前取的是集合中出现过的数的概率是\(\frac{i}{n}\)。所以可得到\(DP\)转移方程\(f[i]=\frac{n-i}{n}f[i+1]+\frac{i}{n}f[i]+1\)。
进一步化简，得\(f[i]=f[i+1]+\frac{n}{n-i}\)。
所以\(f[0]=\sum_{i=1}^n\frac{n}{i}\)。
进阶：
亚瑟王思考后，容易转化成\(ans=\sum dp[i]*d[i]\)，其中,\(dp[i]\)表示第\(i\)张卡在\(r\)轮中打出的概率。
考虑如何计算\(dp[i]\)。
由于每一轮打出一张卡后，该轮结束，所以每张卡在\(r\)轮中被打出的概率与在它前面有多少张卡被打出有关。
设\(f[i][j]\)表示在\(r\)轮中，前\(i\)张卡被打出了\(j\)张的概率，在此情况下，第\(i+1\)张牌在\(r\)轮中有\((1-p[i+1])^{r-j}\)的概率未被打出，再用\(1\)减去，就得到了打出的概率。所以枚举\(k\)得到：\(dp[i]=\sum f[i-1][k]*(1-(1-p[i])^{r-k})\)。
现在考虑如何计算\(f[i][j]\)。
递推。当前的第\(i\)张卡选或不选。 选：\(f[i][j]+=f[i-1][j-1]*(1-(1-p[i])^{r-j+1})\)。\((j\neq 0)\) 不选：\(f[i][j]+=f[i-1][j]*((1-p[i])^{r-j})\)。\((i\neq j)\)
边界：\(f[1][1]=dp[1]=1-(1-p[1])^r\)\(f[1][0]=(1-p[1])^r\)
本题得到解决。（注意精度！）
概率充电器\(WA\)了无数遍。。。有一个坑人的小细节。。。
思考后，可转换成\(ans=\sum (1-res[i])\)。其中，\(res\)表示节点\(i\)未被充电的概率。
强制把这棵树转化为有根树，我们可以发现，对与任意非根节点，它能否被点亮取决于它的子节点以及它的父亲。想到树形\(DP\)。
我们设\(f[i]\)，\(g[i]\)分别表示\(i\)不被它的子节点点亮的概率，\(i\)不被它父亲点亮的概率。
所以\(res[i]=f[i]\times g[i]\)。
现在思考如何求\(f[i]\)。
第一遍\(dfs\)遍历时，直接 \(f[i]=(1-p[i])\times \prod_{son\in i}\lgroup1-(1-f[son]\times val(i,son))\rgroup\)，无需过多的解释。
由于根节点无父节点，所以\(g[root]=1\)，即\(res[root]=f[root]\)现在，思考如何求非根节点的\(g[i]\)。
做到这里，我先前有个抽风的想法，以为直接可以\(g[v]=ans[u]+(1-ans[u])\times (1-val(u,v))\)(\(v\)是\(u\)的子节点)，当\(WA\)到怀疑人生时才想到这是错误的。。。想想为什么？
请注意，\(g[i]\)的状态定义是：\(i\)不被它父亲点亮的概率，所以不管子节点鸟事。。。即默认为\(v\)不带电，所以我们需要把\(ans[u]\)除去先前乘进\(f[i]\)中的\(v\)子树中不带电的概率。
即\(P=\frac{g[i]\times f[i]}{1-(1-f[v]\times val(u,v))}\)，\(g[v]=P+(1-P)\times (1-val(u,v))\)。
本题得到\(O(n)\)解决。
奖励关\(doing...\)
迷失游乐园\(doing...\)
转载于:https://www.cnblogs.com/silentEAG/p/11192670.html
