动态规划-简单了解下什么是期望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−p1​p2​×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