[LeetCode]Soup Servings

首先因为我们每一次的操作都是25的倍数，我们可以把输入数据除以25即可，有余数的话加一。其次我们可以用DP的思路解决这道题，dp[i][j]表示当前状态为i毫升A和j毫升B的概率，那么我们有递推方程：

• dp[i][j] = 0.25 * dp[1 + 4][j] + 0.25 * dp[i + 3][j + 1] + 0.25 * dp[i + 2][j + 2] + 0.25 * dp[i + 1][j + 3]

这个很好理解，就是通过四个操作可以达到当前状态，每个操作的概率是0.25。特殊情况是i和j同时达到小于等于0的状态时，我们按题目所述取一半。另外所有i <= 0 && j <= 0的状态我们都归结到dp[0][0]以简化计算。假设输入为N毫升，时间复杂度为O(N^2)，空间复杂度同样。代码如下：

考虑到输入的规模，这样的代码在处理较大值的时候毫无疑问会MLE。由于输入最多可以达到10^9，我们在空间方面并没有太多的优化空间，即使优化到1D也仍旧会MLE。参考了解法之后，解法中给出了分析当输入N足够大的之后，先用完A的概率是无限趋近于1的，基本上N超过5000的话，我们就可以直接return 1了。所以我们只需要对数据规模在5000一下的test case跑DP的方法；5000以上的直接return。代码如下：