题目

808. 分汤【中等】

题解

动态规划

由于四种分配操作都是25的倍数，因此可以先将n同除以25，四种分配操作变成（4,0），（3,1），（2,2），（1,3），且每种分配概率为0.25。
n较小时，可以用动态规划解决，

1. 状态定义：dp[i][j] 表示汤 A 和汤 B 分别剩下 i 和 j 份时的所求概率值。
2. 状态转移方程：四种分配操作
   dp[i][j]=1/4(dp[i−4][j]+dp[i−3][j−1]+dp[i−2][j−2]+dp[i−1][j−3])dp[i][j]=1/4(dp[i-4][j]+dp[i-3][j-1]+dp[i-2][j-2]+dp[i-1][j-3])dp[i][j]=1/4(dp[i−4][j]+dp[i−3][j−1]+dp[i−2][j−2]+dp[i−1][j−3])
3. 初始条件：
   i>0，j=0：B分配完了，但A没有，此时A也无法分配了，dp[i][j]=0+0=0
   i=0，j=0：A,B同时分配完，因此dp[i][j]=0+0.5*1=0.5
   i=0，j>0：A分配完了，而B还没有，根据四种分配操作B也没法分配了，所以A先分配完的概率为1，dp[i][j]=1+0=1
4. 返回值：dp[n][n]

动态规划的时间复杂度为O(n2)O(n^2)O(n2)，除以25之后依然无法在短时间内得到答案
计算A先分配完的数学期望E(A)=（4+3+2+1）*0.25=2.5，B先分配完的数学期望E(B)=（0+1+2+3）*0.25=1.5，当n非常大时，认为A先被分配完的概率接近于1
动态规划可得这个很大的n的临界值为4475(=179*25)，所以n大于这个值时，直接返回概率1

class Solution {public double soupServings(int n) {n=(int)Math.ceil((double)n/25);//ceil天花板取整if(n>179)return 1;double[][] dp=new double[n+1][n+1];dp[0][0]=0.5;for(int i=1;i<=n;i++)dp[0][i]=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=(dp[Math.max(0,i-4)][j]+dp[Math.max(0,i-3)][Math.max(0,j-1)]+dp[Math.max(0,i-2)][Math.max(0,j-2)]+dp[Math.max(0,i-1)][Math.max(0,j-3)])/4.0;}}return dp[n][n];}
}

时间复杂度：O(C2)O(C^2)O(C2)

空间复杂度：O(C2)O(C^2)O(C2)