动态规划-简单了解下什么是期望DP-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划-简单了解下什么是期望DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

首先说明下为啥是简单了解下，因为对于期望DP的问题，相较于一般的动态规划问题，可以说期望DP的题目相对较少，并且往往具有一定的难度。这是因为期望DP在解决问题时需要考虑状态的期望值，涉及到概率和随机性的计算，因此可能需要运用更多的数学知识和技巧，所以我们作为入门还是了解下。

期望DP是一种动态规划的应用方法，用于解决具有期望值的问题。在许多问题中，我们不仅关心某个状态的具体值，还关心该状态的期望值，即在多次实验中，该状态的平均值。期望DP就是利用动态规划的思想，计算解决具有期望值的问题。

在期望DP中，我们将问题转化为求解状态的期望值，而不仅仅是状态的具体值。通过定义状态和状态转移方程，我们可以递推计算得到状态的期望值，从而求解问题。通常，期望DP与普通的动态规划方法类似，但需要在状态转移方程中加入期望值的计算。

期望DP的一个难度在于没有一个固定的模板，只有一个大致框架：

#include <iostream>
#include <vector>

using namespace std;

// 定义全局变量
const int MAX_N = 1000;
double dp[MAX_N];  // 存储状态值

double expectedDP(int n) {
    // 初始化边界条件
    dp[0] = 0;  // 根据具体问题进行初始化

    // 动态规划状态转移
    for (int i = 1; i <= n; i++) {
        // 定义状态转移方程
        dp[i] = (/*根据具体问题定义转移方程*/);
    }

    return dp[n];  // 返回最终的期望值
}

int main() {
    int n;
    cin >> n;

    cout << "Expected DP: " << expectedDP(n) << endl;

    return 0;
}

dp 数组用于存储不同状态下的期望值。因为是大致框架，你需要根据具体的问题定义状态转移方程中的计算逻辑。在实际使用中，根据问题的不同，可能需要引入更多的辅助变量和数据结构来存储和计算期望值。
我们同样通过一道例题来对期望DP的实际应用留下印象。题目的意思是说一个游戏里面对英雄进行分类，一共有 nn 种职业， mm 种阵营。小蓝每天玩一个英雄，这个英雄属于某一种职业，也属于某一种阵营。每个英雄属于某个职业的概率是 1nn1 ，属于某种阵营的概率是 1mm1 。求小蓝玩遍了所有职业和阵营的期望天数。

大致思路：

令 dp[i][j] 为小蓝已经玩过 i 种职业，j个阵营之后，达到最终状态的期望天数。这里的最终状态是玩遍所有的职业与阵营。

那么我们可以得到 dp[n][m]=0 ，因为已经达到了目标状态，所以我们可以倒推，我们要求的答案就是 dp[0][0]。（求概率一般是正推，求期望一般是逆推）。

考虑 dp[i][j]的状态转移：

目前玩的英雄的职业和阵营之前都玩过，转移到 dp[i][j] ，概率为 p1= i/n * j/m 。
目前玩的英雄的职业玩过，阵营没玩过，转移到 dp[i][j+1]，概率为 p2=i/n * (m - j)/m 。
目前玩的英雄的职业没玩过，阵营玩过，转移到 dp[i+1][j] ，概率为 p3=(n - i)/n * j/ m。
目前玩的英雄的职业和阵营都没玩过，转移到 dp[i+1][j+1]，概率为 p4=(n - i)/n * (m - j)/m 。

再根据期望的线性性质，可以得到转移方程为：

dp[i][j]=p1×dp[i][j]+p2×dp[i][j+1]+p3×dp[i+1][j]+p4×dp[i+1][j+1]+1dp[i][j]=p1×dp[i][j]+p2×dp[i][j+1]+p3×dp[i+1][j]+p4×dp[i+1][j+1]+1 。

这里最后的 +1 是因为要消耗一天来玩英雄。之后移项可以得到：

(1−p1)dp[i][j]=p2×dp[i][j+1]+p3×dp[i+1][j]+p4×dp[i+1][j+1]+1(1−p1)dp[i][j]=p2×dp[i][j+1]+p3×dp[i+1][j]+p4×dp[i+1][j+1]+1 。

再把系数除过去得到：

dp[i][j]=p2×dp[i][j+1]+p3×dp[i+1][j]+p4×dp[i+1][j+1]+11−p1dp[i][j]=1−p1p2×dp[i][j+1]+p3×dp[i+1][j]+p4×dp[i+1][j+1]+

(最后经过数学方法移项将p1,p2,p3,p4带入即可)。

原题链接：

https://www.lanqiao.cn/problems/4337/learning/?page=1&first_category_id=1&name=%E5%B0%8F%E8%93%9D%E7%8E%A9%E6%B8%B8%E6%88%8F文章来源地址https://www.toymoban.com/news/detail-836549.html

到了这里，关于动态规划-简单了解下什么是期望DP的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！