力扣(LeetCode)808. 分汤(C++)

动态规划

如图，本题的状态表示，是二维 $dp$ $f[i,j]$ ， $i$ 表示剩余的 $a$ ， $j$ 表示剩余的 $b$ ， $f[i,j]$ 表示 $a$ 先取完的概率 。

按照 $i/j$ 的剩余数量做集合划分
①当 $i\le 0,j\le 0$ ， $a/b$ 同时取完 ， 线性概率 $f[i][j]=1.0÷2=0.5$
②当 $i\le 0,j>0$ ， $a$ 先取完 ， $f[i][j]=1.0$
③当 $i>0,j\le 0$ ， $b$ 先取完 ， $f[i][j]=0.0$
④当 $i>0,j>0$ ， $a/b$ 都有剩余 ， 有均等概率进行 $4$ 种取法 ， 为了便于操作 ， 将所有取法的取值 $÷25$ ， 那么初始汤量 $n=n÷25$ ， $f[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]=\{\begin{array}{ll}0.5& \text{if }i\le 0,j\le 0\\ 1.0& \text{if }i\le 0,j>0\\ 0.0& \text{if }i>0,j\le 0\\ (f[i-4][j]+f[i-3][j-1]+f[i-2][j-2]+f[i-1][j-3])÷4& \text{if }i>0,j>0\end{array}$

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

朴素dp

class Solution {
public:
    int g(int x){//分汤后小于0，归为0
        return max(0,x);
    }
    double soupServings(int n) {
        // n = (n+24)/25;//向上取整
        n = n / 25 + (n%25!=0);
        if(n>=189) return 1;
        vector<vector<double>> f(n+1,vector<double>(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

AC