本文从WordPress迁移而来, 查看全部WordPress迁移文章
【重做DP系列】 期望dp,记忆化搜索实现
题意:给一个数字n<=1(不一定是质数),选小于等于n的质数,如果n能被该质数整除,就变为n = n/质数,如果不能整除,n保持不变。选了一个质数,能不能整除都算作一步。问n变为1,期望步数是多少
先设置几个量,tot表示小于等于n的质数个数,cnt表示这些质数里哪些能整除n,dp[n]表示n对应的期望步数
dp[n] = p0 dp[n] + p1 dp[x1] + p1 dp[x2] + …… + p1 dp[xm] + 1
P1表示选中某个质数可以整除n的概率,使得n变为xi,可知p1 = 1/tot,每个质数没选中的概率都是1/tot。中间部分容易理解,第1项表示选中一个质数不能被n整数,概率为p0,p0 = (tot-cnt)/tot = 1 - cnt/tot。后面+1是因为无论都付出一个步数
我们可以通过移向来变换公式
1 | (1-p0) dp[n] = p1 * dp[x1] + p1 * dp[x2] + ....... + p1 * dp[xm] + 1 |
所以我们只需要预处理出tot和cnt就行了,其实不同预处理,只要筛好质数,保存下来就行了,详细见代码
1 |
|