这个题读明白题后大概就有思路了，模拟，可以递归也可以使用动态规划来模拟分汤的过程。

但这个题的难点在对于数据的处理，不然非常容易超时

我们可以发现每次处理分出去的为25的倍数，因此可以对n除以25向上取整，求出n可以分出几份。这样减少了数据规模。

还有一个难点在于，对于当汤的数量非常大的时候，概率会无限接近于1，而题目又表明

返回值在正确答案 10−510^{-5}10−5 的范围内将被认为是正确的。

因此可以求出来当n大于某个数的时候，与1的差将小于10−510^{-5}10−5此时可以直接返回1。通过测试可以得出

n=4475,p≈0.999990211307
n=4476,p≈0.999990468596

因此n≥179×25时，可以直接返回1

记忆化递归

class Solution {
public:vector> f;double func(int a, int b){if(a <= 0 && b > 0)return 1;if(a <= 0 && b <= 0)return 0.5;if(a > 0 && b <= 0)return 0;if(f[a][b] != 0)return f[a][b];double sum = 0;sum += func(a - 4, b);sum += func(a - 3, b - 1);sum += func(a - 2, b - 2);sum += func(a - 1, b - 3);sum *= 0.25;f[a][b] = sum;return sum;}double soupServings(int n) {if(n % 25 == 0)n = n / 25;elsen = n / 25 + 1;if(n >= 179)return 1;f = vector>(n + 1, vector(n + 1, 0));return func(n, n);}
};

动态规划

class Solution {
public:double soupServings(int n) {if(n % 25 == 0)n = n / 25;elsen = n / 25 + 1;if(n >= 179)return 1.0;vector> dp(n + 1, vector(n + 1, 0));for(int i = 0; i < n + 1; i++)dp[0][i] = 1;dp[0][0] = 0.5;for(int i = 1; i < n + 1; i++){for(int j = 1; j < n + 1; j++){double sum = 0;sum += dp[max(i - 4, 0)][max(j, 0)];sum += dp[max(i - 3, 0)][max(j - 1, 0)];sum += dp[max(i - 2, 0)][max(j - 2, 0)];sum += dp[max(i - 1, 0)][max(j - 3, 0)];dp[i][j] = 0.25 * sum;}}return dp[n][n];}
};