虽然我们知道，数学期望DP很多时候是要靠感性理解的
但是这道题目显然可以列出所有样本空间去考虑，在这种情况下我们就严谨一点
我们先设\(f[i][j]\)表示前\(i\)个课程申请了\(j\)个课程的最小期望路径
我们先考虑第\(i\)个课程不申请，那么\(j\)个课程全部都申请到了前\(i-1\)个课程里面
我们要想转移到\(f[i][j]\)，就必须要知道在第\(i-1\)的课程的时候我们在哪个教室
如果我们第\(i-1\)个课程没申请，那么可以通过样本空间知道这个时候的概率是\(1\)
如果我们第\(i-1\)个课程申请了，那么前面的样本空间又要被分成两批，一批的终点是\(a[i-1]\)教室，概率是\(1-p[i-1]\)；一批的终点是\(b[i-1]\)教室，概率是\(p[i-1]\)；然后再用对应的概率去乘以对应的路径
但是你就会发现这里就转移不走了：我们目前的状态没办法分清这么多信息
所以我们加维，从上述分析过程中不难得到，设\(f[i][j][0/1]\)表示前\(i\)个课程申请了\(j\)个课程且第\(i\)个课程是否申请的最小期望路径
然后就可以推走了
标签：概率,课程,申请,教室,样本空间,我们 From： https://www.cnblogs.com/dingxingdi/p/18017819