当前位置: 首页 > news >正文

概率DP和期望DP

概率DP&期望DP

入门而已啦QAQ

两者好像是属于同一类问题(?

但思路总体恰恰相反:

概率DP:

采用顺推,也就是从初始状态推向结果。

期望DP:

采用逆推,从末状态推向结果。

(可能有点抽象

看几道经典例题吧!

概率DP

1. Bag of mice

思路:

我们分类讨论所有情况,

f [ i ] [ j ] f[i][j] f[i][j]为轮到公主时袋子里有 i i i 只白鼠, j j j 只黑鼠,公主赢的概率。

初始化边界, f [ 0 ] [ i ] = 0 f[0][i] = 0 f[0][i]=0因为没有白鼠了算龙赢, f [ i ] [ 0 ] = 1 f[i][0]=1 f[i][0]=1因为抓一只就是白鼠,公主赢。 考虑 f [ i ] [ j ] f[i][j] f[i][j] 的转移:

  • 公主抓到一只白鼠,公主赢了。概率为 i i + j \frac{i}{i + j} i+ji
  • 公主抓到一只黑鼠,龙抓到一只白鼠,龙赢了。概率为 j i + j × i i + j − 1 \frac{j}{i+j}\times \frac{i}{i + j - 1} i+jj×i+j1i
  • 公主抓到一只黑鼠,龙抓到一只黑鼠,跑出来一只黑鼠,转移到 f [ i ] [ j − 3 ] f[i][j-3] f[i][j3]。概率为 j i + j × j − 1 i + j − 1 × j − 2 i + j − 2 \frac {j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2} i+jj×i+j1j1×i+j2j2
  • 公主抓到一只黑鼠,龙抓到一只黑鼠,跑出来一只白鼠,转移到 f [ i − 1 ] [ j − 2 ] f[i-1][j-2] f[i1][j2]。概率为 j i + j × j − 1 i + j − 1 × i − 1 i + j − 2 \frac{j}{i+j}\times \frac{j-1}{i+j-1}\times\frac{i-1}{i+j-2} i+jj×i+j1j1×i+j2i1

一定只有这四种情况!

考虑公主赢的概率,第二种情况不参与计算。并且要保证后两种情况合法,所以还要判断 i , j i,j i,j 的大小,满足第三种情况至少要有 3 3 3 只黑鼠,满足第四种情况要有 1 1 1 只白鼠和 2 2 2 只黑鼠。

然后是简简单单的代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const int N = 1010;

double f[N][N];//轮到公主,有i个白鼠j个黑鼠,公主赢的概率
int a, b;

void solve()
{
    cin >> a >> b;
    for (int i = 0; i <= a; i++) f[i][0] = 1;
    for (int i = 0; i <= b; i++) f[0][i] = 0;
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
        {
            f[i][j] += 1.0 * i / (i + j);
            if (j > 2) f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j - 3];
            if (i > 0 && j > 1) f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i - 1][j - 2];
        }
    printf("%.9f", f[a][b]);
}
signed main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int T = 1;// cin >> T;
    while(T--) solve();
    return 0;
}

2. Jon and Orbs

转移方程好好推捏,但代码实现(对憨憨)很不友好!

还是分类讨论:

f [ i ] [ j ] f[i][j] f[i][j] i i i天产生了 j j j种球的概率,他能转移到两种情况:第 j + 1 j+1 j+1天产生的是和以前相同种类的球,概率是 i k \frac{i}{k} ki,转移到状态 f [ i ] [ j + 1 ] f[i][j+1] f[i][j+1]和第 j + 1 j+1 j+1天产生了一种新的类型的球,概率为 k − i k \frac{k-i}{k} kki,转移到状态 f [ i + 1 ] [ j + 1 ] f[i+1][j+1] f[i+1][j+1].

那么我们可以得到转移方程为:

f[i][j] = j / k * f[i][j + 1] + (k - j) / k * f[i + 1][j + 1]

但这是逆推,末状态我们是不知道的,我们只能知道初状态

f[0][0] = 1 && f[i][0] = 0(i != 0)

所以我们将思维逆转一下:

f [ i ] [ j ] f[i][j] f[i][j] i i i天产生了 j j j种球的概率,他能从两种情况转移而来:第 j j j天产生的是和以前相同种类的球,概率是 i k \frac{i}{k} ki,从状态 f [ i ] [ j − 1 ] f[i][j-1] f[i][j1]转移过来和第 j j j天产生了一种新的类型的球,概率为 k − ( i − 1 ) k \frac{k-(i-1)}{k} kk(i1),从状态 f [ i − 1 ] [ j − 1 ] f[i-1][j-1] f[i1][j1]转移过来.

那么我们可以得到转移方程为:

f[i][j] = j / k * f[i - 1][j] + (k - j + 1) / k * f[i - 1][j - 1]
//我们可以发现,下一维的i用的是上一维的i的数据,那么我们可以借助滚动数组采取逆序枚举来实现对第一维的优化
//注意f[i][0] = (i == 0 ? 0 : 1);

根据已知的初状态我们就可以求解了

#include <bits/stdc++.h>
#define endl '\n'
// #define int long long
 
using namespace std;
 
const int N = 1010;
 
// double f[N][N];
double f[N];//第一维用滚动数组实现
int day[N];
 
void solve()
{
    int k, q;
    cin >> k >> q;
    // f[0][0] =1;
    f[0] = 1;//当i==0时,f[i][0] = 1, 否则f[i][0] = 0
    int p = 1;
    for (int i = 1; p <= 1000; i++)
    {
        for (int j = k; j >= 1; j--)
        {
            // f[j] = (j * f[j] + (k - j + 1) * f[j - 1]) / k; //√
            f[j] = 1.0 * j / k * f[j] + 1.0 * (k - j + 1) / k * f[j - 1];//注意i,j都是整数,运算得不到想要的浮点数,所以别忘了精度转换!!!!!!!
        }
        while (f[k] * 2000 >= p + 1e-7) day[p] = i, p++;//只要第i天后的概率满足该pi,就一直记录答案直到不满足,继续循环下一天
        f[0] = 0;//之后用到的都是i>0的一层的结果,所以要改成0
    }    
    while(q--)//因为有多次询问,我们将所有的pi对应哪一天都预处理出来存在数组中
    {
        int x; cin >> x;
        printf("%d\n", day[x]);
    }
}
signed main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int T = 1;// cin >> T;
    while(T--) solve();
    return 0;
}

期望DP

1. Collecting Bugs

f [ i ] [ j ] f[i][j] f[i][j] 为已经找到 i i i 种 bug 分类, j j j 个子系统的 bug,达到目标状态的期望天数。这里的目标状态是找到 n n n 种 bug 分类, s s s 个子系统的 bug。那么就有 f [ n ] [ s ] = 0 f[n][s]=0 f[n][s]=0 ,因为已经达到了目标状态,不需要用更多的天数去发现 bug 了,于是就以目标状态为起点开始递推,答案是 f [ 0 ] [ 0 ] f[0][0] f[0][0]

考虑 的状态转移:

  • f [ i ] [ j ] f[i][j] f[i][j]发现一个 bug 属于已经发现的 i i i 种 bug 分类, j j j 个子系统,概率为 p 1 = i n × j s p_1=\frac{i}{n}\times \frac{j}{s} p1=ni×sj
  • f [ i ] [ j + 1 ] f[i][j+1] f[i][j+1],发现一个 bug 属于已经发现的 i i i 种 bug 分类,不属于已经发现的子系统,概率为 p 1 = i n × s − j s p_1=\frac{i}{n}\times \frac{s-j}{s} p1=ni×ssj
  • f [ i + 1 ] [ j ] f[i+1][j] f[i+1][j],发现一个 bug 不属于已经发现 bug 分类,属于 j j j 个子系统,概率为 p 1 = n − i n × j s p_1=\frac{n-i}{n}\times \frac{j}{s} p1=nni×sj
  • f [ i + 1 ] [ j + 1 ] f[i+1][j+1] f[i+1][j+1],发现一个 bug 不属于已经发现 bug 分类,不属于已经发现的子系统,概率为 p 1 = n − i n × s − j s p_1=\frac{n-i}{n}\times \frac{s-j}{s} p1=nni×ssj

再根据期望的线性性质,就可以得到状态转移方程:

f[i][j] = p1 * f[i][j] + p2 * f[i][j + 1] + p3 * f[i + 1][j] + p4 * f[i + 1][j + 1]
//一定要化简后才能用来转移,因为我们要得到f[i][j]状态,只有等式左边才能有f[i][j],右边不能有!!!
//化简后
f[i][j] = ((j - s) * (i - n) * f[i + 1][j + 1] + j * (n - 2) * f[i + 1][j] + i * (s - j) * f[i][j + 1] + n * s) / (n * s - i * j)

简单的代码:

// #include <bits/stdc++.h>
#include <iostream>
#define endl '\n'
// #define int long long

using namespace std;

const int N = 1010;

int n, s;
double f[N][N];

void solve()
{
    cin >> n >> s;
    f[n][s] = 0;
    for (int i = n; i >= 0; i--)
        for (int j = s; j >= 0; j--)
        {
            if (i == n && j == s) continue;
            // f[i][j] =  f[i][j] * i / n * j / s  
            // + f[i + 1][j] * (n - i) / n * j / s 
            // + f[i][j + 1] * i / n * (s - j) / s  
            // + f[i + 1][j + 1] * (n - i) / n * (s - j) / s  
            // + 1;
            //未化简,不能用来状态转移哦
            f[i][j] = (f[i + 1][j + 1] * (j - s) * (i - n) + f[i + 1][j] * j * (n - i) + f[i][j + 1] * i * (s - j) + n * s) / (n * s - i * j);
        }
    printf("%.4f", f[0][0]);
}
signed main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int T = 1;// cin >> T;
    while(T--) solve();
    return 0;
}

未完待续(希望如此。。。

相关文章:

  • 项目管理逻辑:项目如何算是做完?什么是项目管理中的PPP模式?
  • 离线安装harbor容器镜像仓库(harbor-v2.3.5)
  • CTFHub | 过滤空格
  • [附源码]计算机毕业设计基于SpringBoot的黄河文化科普网站
  • ConcurrentHashMap 1.7与1.8的区别
  • 中序遍历迭代算法(非递归算法)
  • 汇编语言与微机原理 期末半开卷复习整理(上)
  • Linux-性能分析常用工具
  • 某验三代滑块流程分析
  • JMeter入门教程(14)——场景设计
  • C#学习记录——在C#中操作注册表
  • 【cocos源码学习】模板示例工程的目录说明
  • UE5 中 LiveLink 的开发全流程教程
  • 力扣(LeetCode)134. 加油站(C++)
  • 学习 MySQL:什么是分页
  • DPD(Digital Pre-Distortion,数字预失真)
  • JAVA毕业设计课程与成绩管理计算机源码+lw文档+系统+调试部署+数据库
  • 分面中添加直线
  • [LeetCode 1774]最接近目标价格的甜点成本
  • 计算卫星高度角、方位角
  • 计算机毕业设计Java企业固定资产管理系统的设计实现(源代码+数据库+系统+lw文档)
  • 实验十一 级数与方程符号求解(MATLAB)
  • [附源码]Python计算机毕业设计Django疫情防控平台
  • Java - 通过反射进行赋值以及函数调用
  • OpUtils的网络扫描
  • 电力系统潮流计算(牛顿-拉夫逊法、高斯-赛德尔法、快速解耦法)【6节点 9节点 14节点 26节点 30节点 57节点】(Matlab代码实现)
  • Kafka消息队列大数据实战教程-第四篇(Kafka客户端Producer API)
  • 【从零开始学习深度学习】12. 什么是模型的训练误差?基于三阶多项式的欠拟合与过拟合训练过程演示
  • 腾讯数字孪生和To B简介
  • 【机器学习】Rasa NLU以及Rasa Core概念和语法简介(超详细必看)
  • 湖南2021本科批(普通类历史类)第一次征集志愿投档分数线
  • 2022年甘肃高考482分能报什么大学 482分能上哪些院校
  • 2022年全国各大高校在山东招生计划及分数
  • 浙江有哪些师范大学,年浙江师范类大学分数线排名一览表
  • 武汉设计工程学院是几本
  • 2022感恩节放假吗 中国有哪些节日会放假
  • 12种新高考3+1+2选科组合分析 怎么选科好
  • 0基础艺考最容易过的专业有哪些 通过率最高的专业是什么
  • 体育高水平怎么报名
  • 浙江2022普通类第二段平行投档分数线是多少