因为A和B减少的期望不同，所以随着N无限增大，A先减少到0的概率无限接近于1题目要求精度为10e-6以内，具体找概率何时精度高于10e-6通过遍历N和dfs打表来看，基本上N>5000就可以。然后dp思路有个trick，就是将25作为一个计算单位，可以减少内存使用。
class Solution {
public:
double soupServings(int N) {
if(N > 5000) return 1;
int C = (N+24)/25;
vector<vector<double> > dp(C+1,vector<double>(C+1,0));
dp[C][C] = 1;
for(int i=C;i>=1;--i){
for(int j=C;j>=1;--j){
double t = dp[i][j] *0.25;
if(i>0) dp[max(0,i-4)][j] += t;
if(i>0&&j>0){
dp[max(0,i-3)][max(0,j-1)] += t;
dp[max(0,i-2)][max(0,j-2)] += t;
dp[max(0,i-1)][max(0,j-3)] += t;
}
}
}
double ans = dp[0][0] * 0.5;
for(int i=1;i<=C;++i) ans += dp[0][i];
return ans;
}
};
Processed:
0.050, SQL:
9
