用动态规划解决排列组合和概率问题

2023-03-19 16:18 作者:yh--123 0人读过 | 我要投稿

动态规划是什么？

baike.baidu.com/item/动态规划/529408?fr=aladdin

能用动态规划解决的问题必须满足未来与过去无关

例1

甲乙丙三个人传球，现在球在甲手上，经过5次传球（球不能自己传给自己），问最终球传回甲手里的路径数目。

先来看看一般的方法是怎么做的

一条条数呗，总共10条。如果经过稍微优化，可以将乙和丙合并成一条权重为2的路径

稍微优化的算法，得到路径数目为2x(2+1+2)=10

然而即使经过优化，此算法在传递次数更大的情况仍麻烦。

那就有请我们的动态规划（DP）上场

$%E8%AE%BES_%7Bi%2Cj%7D%20%E4%B8%BA%E7%BB%8F%E8%BF%87i%E6%AC%A1%E4%BC%A0%E9%80%92%E5%90%8E%EF%BC%8C%E7%90%83%E6%9C%80%E7%BB%88%E8%90%BD%E5%88%B0%E7%AC%ACj%E5%8F%B7%E4%BA%BA%E5%91%98%E6%89%8B%E9%87%8C%E7%9A%84%E8%B7%AF%E5%BE%84%E6%95%B0%E7%9B%AE$

$%E7%94%B2%E4%B8%BA%E7%AC%AC1%E5%8F%B7%E4%BA%BA%E5%91%98%E3%80%82%E7%89%B9%E5%88%AB%E5%9C%B0%EF%BC%8Ci%3D0%E8%A1%A8%E7%A4%BA%E5%88%9D%E6%80%81$

得状态转移方程 $S_%7Bi%2Cj%7D%20%3D(%5Csum_%7Bk%3D1%7D%5E3%20S_%7Bi-1%2Ck%7D%20)-S_%7Bi-1%2Cj%7D%3D3%5E%7Bi-1%7D-S_%7Bi-1%2Cj%7D$

观察表格得到规律：传到甲手里得路径数总是和其他人相差1

当i为偶数时，甲多1；当i为奇数时，甲少1；

得到通项公式

$S_%7Bi%2C1%7D%3D%5Cfrac%7B2%5Ei%2B1%20%7D%7B3%7D%20-1%3D%5Cfrac%7B2%5Ei-2%20%7D%7B3%7D(i%E4%B8%BA%E5%A5%87%E6%95%B0)$ $S_%7Bi%2Cj%7D%3D%5Cfrac%7B2%5Ei-2%20%7D%7B3%7D%20%2B1%3D%5Cfrac%7B2%5Ei%2B1%20%7D%7B3%7D(i%E4%B8%BA%E5%A5%87%E6%95%B0%2Cj%5Cneq1%20)$

$S_%7Bi%2C1%7D%3D%5Cfrac%7B2%5Ei-1%20%7D%7B3%7D%20%2B1%3D%5Cfrac%7B2%5Ei%2B2%20%7D%7B3%7D(i%E4%B8%BA%E5%81%B6%E6%95%B0)$ $S_%7Bi%2Cj%7D%3D%5Cfrac%7B2%5Ei%2B2%20%7D%7B3%7D%20-1%3D%5Cfrac%7B2%5Ei-1%20%7D%7B3%7D(i%E4%B8%BA%E5%81%B6%E6%95%B0%2Cj%5Cneq%201)$

进而无论传几次，传到谁手里，方案数都能很快地算出来。

容易推广到m个人，传n次，传到自己手里的路径数

$S_%7Bi%2C1%7D%3D%5Cfrac%7B(m-1)%5Ei%2B1%20%7D%7Bm%7D%20-1%3D%5Cfrac%7B(m-1)%5Ei-(m-1)%20%7D%7Bm%7D(i%E4%B8%BA%E5%A5%87%E6%95%B0)$ $S_%7Bi%2C1%7D%3D%5Cfrac%7B(m-1)%5Ei-1%7D%7Bm%7D%20%2B1%3D%5Cfrac%7B(m-1)%5Ei%2B(m-1)%20%7D%7Bm%7D(i%E4%B8%BA%E5%81%B6%E6%95%B0)$

传到别人手里的路径数 $S_%7Bi%2Cj%7D%3D%5Cfrac%7B(m-1)%5Ei-(m-1)%20%7D%7Bm%7D%20%2B1%3D%5Cfrac%7B(m-1)%5Ei%2B1%20%7D%7Bm%7D(i%E4%B8%BA%E5%A5%87%E6%95%B0%2Cj%5Cneq1%20)$

$S_%7Bi%2Cj%7D%3D%5Cfrac%7B(m-1)%5Ei%2B(m-1)%20%7D%7Bm%7D%20-1%3D%5Cfrac%7B(m-1)%5Ei-1%20%7D%7Bm%7D(i%E4%B8%BA%E5%81%B6%E6%95%B0%2Cj%5Cneq1%20)$

加强1

甲乙丙丁戊……共11人，球在甲手里，经过100次传球（球不能自己传给自己），问最终球传回甲手里的路径数目。

答案： $%5Cfrac%7B10%5E%7B100%7D%20%2B10%7D%7B11%7D%20$

例2 甲乙丙丁戊五个桶，甲最多能装5个球，乙最多能装8个球，丙最多能装11个球，丁最多7，戊最多3，现有17个完全相同的小球，问装进5个桶中的方案数量（可空桶）。

先假设它没有最大限制吧

削弱1 甲乙丙丁戊五个桶，现有17个完全相同的小球，问装进5个桶中的方案数量（可空桶）。

答案是 $C_%7B21%7D%5E4$ =5985

如果用动态规划解决呢?

将甲、乙、丙、丁、戊编号为1、2、3、4、5

$%E8%AE%BES_%7Bi%2Cj%7D%E4%B8%BA%E5%B0%86j%E4%B8%AA%E5%B0%8F%E7%90%83%E6%94%BE%E5%85%A5%E5%89%8Di%E4%B8%AA%E6%A1%B6%E5%86%85%E7%9A%84%E6%96%B9%E6%A1%88%E6%95%B0$

状态转移方程 $S_%7Bi%2Cj%7D%3D%5Csum_%7Bk%3D0%7D%5Ej%20S_%7Bi-1%2Ck%7D%20(i%3E1)$

细心的人已经发现了，这就是杨辉三角的表格版。用了DP反而更加麻烦了

那么有了最大限制呢？

传统的办法是分类讨论，其实这已经类似于DP了。

DP解法：将甲、乙、丙、丁、戊编号为1、2、3、4、5

$%E8%AE%BES_%7Bi%2Cj%7D%E4%B8%BA%E5%B0%86j%E4%B8%AA%E5%B0%8F%E7%90%83%E6%94%BE%E5%85%A5%E5%89%8Di%E4%B8%AA%E6%A1%B6%E5%86%85%E7%9A%84%E6%96%B9%E6%A1%88%E6%95%B0$

$%E8%AE%BEtop%5Bi%5D%E4%B8%BA%E7%AC%ACi%E4%B8%AA%E6%A1%B6%E8%83%BD%E8%A3%85%E7%9A%84%E6%9C%80%E5%A4%A7%E7%90%83%E6%95%B0$

状态转移方程 $S_%7Bi%2Cj%7D%3D%5Csum_%7Bk%3Dmax(0%2Cj-top%5Bi%5D)%7D%5Ej%20S_%7Bi-1%2Ck%7D%20(i%3E1)$

得到最终答案1486

如果在考试的时候遇到这么死妈的题，强烈建议DP，空间换取时间

例3

M,N两个暗箱。M中有3个黑球，N中有三个白球。将 “M，N各取一球并放到对方的箱子中” 执行6次，问最终M箱含3个白球的概率。

先把M和N可能的状态列出来并标号，用（a,b）表示a个黑球，b个白球

X只是一个代号，表示M和N所处的状态。

用 $X_i$ 表示经过 $i$ 次操作后M和N的状态（特别地， $X_0$ 为初态）

图中红色的4表示 $X_i$ =1时 $X_%7Bi%2B1%7D$ =2的权重为4，即概率为 $%5Cfrac%7B4%7D%7B9%7D%20$

先来试试传统的枚举法

得到

$P(X_6%3D3)%3D%5Cfrac%7B1%5Ctimes4%5E2%5Ctimes9%5Ctimes6%2B4%5E4%5Ctimes8%7D%7B9%5E5%7D%20%3D%5Cfrac%7B2912%7D%7B3%5E%7B10%7D%7D%20$

枚举法太容易漏情况了，我之前做就漏了俩个。

然后是动态规划的方法

$%E8%AE%BES_%7Bi%2Cj%7D%E4%B8%BAX_i%3Dj%E7%9A%84%E6%9D%83%E9%87%8D%EF%BC%8C%E7%89%B9%E5%88%AB%E5%9C%B0%EF%BC%8Ci%3D0%E6%97%B6%E4%B8%BA%E5%88%9D%E6%80%81%EF%BC%8C%E5%BE%97%E5%88%B0%E7%8A%B6%E6%80%81%E8%BD%AC%E7%A7%BB%E6%96%B9%E7%A8%8B$