https://leetcode.com/problems/soup-servings/description/
808. Soup Servings
你現在有兩種湯要分給一群人，給你一個 n 表示這兩種湯的 ml 數量，我們有四種分湯
的方法：
1.A分出100ml B分出0ml
2.A分出75ml B分出25ml
3.A分出50ml B分出50ml
4.A分出25ml B分出75ml
求出依照上述四種分湯的方法，A種類的湯會先被分完的機率，如果A和B同時分完則機率
是50%。
Example 1:
Input: n = 50
Output: 0.62500
Explanation: If we choose the first two operations, A will become empty first.
For the third operation, A and B will become empty at the same time.
For the fourth operation, B will become empty first.
So the total probability of A becoming empty first plus half the probability
that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) =
0.625.
Example 2:
Input: n = 100
Output: 0.71875
思路：
1.對四個選擇進行DFS，如果滿足A先沒的話機率就為1，如果同時沒則機率為0.5。
2.加入一個 memo 記憶已算過的分配比率。
3.然後吃了MLE = = ，實在是不懂要怎麼繼續優化，看了一下其他人的解當 n 越大
的時候，A被先分配完的機率會越來越高（因為分配方式2/3對A有利），因為題目
說實際答案和你給的答案相差在 10^-5 之間可以接受 ，所以當 n 大到一個程度
的時候機率會是 0.99999xxxxxx 這個時候我們直接返回 1 就可以了，只能一個數
字一個數字跑看跑到哪個 n 之後精度可以忽略，當 n = 4450 的時候誤差為：
1 - 0.9999893866772255 = 0.00001061332 ，所以當 n 高於這個數字直接返回
1 就好。
Java Code：
------------------------------------------------------------
class Solution {
private Double[][] memo;
public double soupServings(int n) {
if(n >= 5000) {
return 1.0;
}
memo = new Double[n + 1][n + 1];
return dfs(n, n);
}
public double dfs(int a, int b) {
if (a <= 0 && b <= 0) {
return 0.5;
}
if (a <= 0) {
return 1.0;
}
if (b <= 0) {
return 0.0;
}
if (memo[a][b] != null) {
return memo[a][b];
}
return memo[a][b] = 0.25 * (dfs(a - 100, b) + dfs(a - 75, b - 25) +
dfs(a - 50, b - 50) + dfs(a - 25, b - 75));
}
}
------------------------------------------------------------
要認真看題目 = =
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1690619746.A.74F.html