动态规划

如图，本题的状态表示，是二维 dpdpdp f[i,j]f[i,j]f[i,j] ， iii 表示剩余的 aaa ， jjj 表示剩余的 bbb ， f[i,j]f[i,j]f[i,j] 表示 aaa 先取完的概率 。

按照 i/ji/ji/j 的剩余数量做集合划分
①当 i≤0,j≤0i\le 0,j\le0i≤0,j≤0 ， a/ba/ba/b 同时取完 ， 线性概率 f[i][j]=1.0÷2=0.5f[i][j]=1.0\div2=0.5f[i][j]=1.0÷2=0.5
②当 i≤0,j>0i\le 0,j>0i≤0,j>0 ， aaa 先取完 ， f[i][j]=1.0f[i][j]=1.0f[i][j]=1.0
③当 i>0,j≤0i> 0,j\le0i>0,j≤0 ， bbb 先取完 ， f[i][j]=0.0f[i][j]=0.0f[i][j]=0.0
④当 i>0,j>0i> 0,j>0i>0,j>0 ， a/ba/ba/b 都有剩余 ， 有均等概率进行 444 种取法 ， 为了便于操作 ， 将所有取法的取值 ÷25\div 25÷25 ， 那么初始汤量 n=n÷25n = n\div25n=n÷25 ， f[i][j]=(f[i−4][j]+f[i−3][j−1]+f[i−2][j−2]+f[i−1][j−3])/4f[i][j]= (f[i-4][j]+f[i-3][j-1]+f[i-2][j-2]+f[i-1][j-3])/4f[i][j]=(f[i−4][j]+f[i−3][j−1]+f[i−2][j−2]+f[i−1][j−3])/4

状态转移方程
f[i][j]={0.5if i≤0,j≤01.0if i≤0,j>00.0if i>0,j≤0(f[i−4][j]+f[i−3][j−1]+f[i−2][j−2]+f[i−1][j−3])÷4if i>0,j>0f[i][j] = \begin{cases} 0.5&\text{if }i\le 0,j\le0\\ 1.0&\text{if }i\le 0,j>0\\ 0.0&\text{if }i> 0,j\le0\\ (f[i-4][j]+f[i-3][j-1]+f[i-2][j-2]+f[i-1][j-3])\div4 &\text{if }i> 0,j>0 \end{cases}f[i][j]=⎩⎪⎪⎪⎨⎪⎪⎪⎧​0.51.00.0(f[i−4][j]+f[i−3][j−1]+f[i−2][j−2]+f[i−1][j−3])÷4​if i≤0,j≤0if i≤0,j>0if i>0,j≤0if i>0,j>0​

数学期望 : 取 a=(4+3+2+1)÷4=2.5a=(4+3+2+1)\div4=2.5a=(4+3+2+1)÷4=2.5 取 b=(3+2+1+0)÷4=1.5b=(3+2+1+0)\div 4=1.5b=(3+2+1+0)÷4=1.5 ，数学期望 a>ba>ba>b ，当 nnn 很大时 ， aaa 先取完的概率趋于 111 。经测试 ， n÷25≥189n\div 25 \ge 189n÷25≥189 时 ， aaa 先取完的概率近似为 111

朴素dp

class Solution {
public:int g(int x){//分汤后小于0，归为0return max(0,x);}double soupServings(int n) {// n = (n+24)/25;//向上取整n = n / 25 + (n%25!=0);if(n>=189) return 1;vector> f(n+1,vector(n+1));for(int i = 0;i<=n;i++)for(int j = 0;j<=n;j++){if(!i&&!j) f[i][j] = 0.5;else if(!i&&j) f[i][j] = 1.0;else if (i&&!j) f[i][j] = 0.0;else{//(i&&j)f[i][j] = (f[g(i-4)][j]+f[g(i-3)][g(j-1)]+f[g(i-2)][g(j-2)]+f[g(i-1)][g(j-3)])/4;}}return f[n][n];}
};

1. 时间复杂度 : O(n2)O(n^2)O(n2) ， 状态转移的时间复杂度 O(n2)O(n^2)O(n2) 。
2. 空间复杂度 : O(n2)O(n^2)O(n2) ， fff 数组的空间复杂度 O(n2)O(n^2)O(n2) 。

AC