力扣-808. 分汤

题目描述

思路及实现

其实这题我一开始根本没想什么动态规划，就想着无脑递归不就行了吗？但是递归存在两个问题：一是超出时间限制，二是超出递归深度。
第一个我们可以利用缓存技术大大压缩时间，但是第二个就必须想其他办法解决了，因为题目给的是0 <= n <= 10^9​​​​​​​，但是仔细观察到题目说返回值在正确答案10^-5的范围内将被认为是正确的，
什么意思呢？就是如果结果> 0.99999那么就是返回1.0。按照题目的分配方法，虽然每个分配方法都是0.25几率，但是肯定是 A 平均分得更多的，也就是说我们能够找到一个θ，使得当n >= θ时，有ans > 0.99999。

动态规划

要找到这个整数，就要使用动态规划来求解了。首先先压缩一下题目给的数据，因为分配方法都是25的倍数，所以可以用(n + 24) // 25来压缩，相应的分配方法变成：(4, 0), (3, 1), (2, 2), (1, 3)。
然后就是找到思路：

接着写出程序即可

class Solution:
    def soupServings(self, n: int) -> float:
        n = (n + 24) // 25
        if n >= 179:
            return 1.0
        dp = [[0.0 for _ in range(n + 1)] for _ in range(n + 1)]
        dp[0][0] = 0.5
        for j in range(1, n + 1):
            dp[0][j] = 1.0
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dp[i][j] = (dp[max(i - 4, 0)][j] + dp[max(i - 3, 0)][j - 1]
                            + dp[max(i - 2, 0)][max(j - 2, 0)] + dp[i - 1][max(j - 3, 0)]) / 4
        return dp[n][n]

深度优先搜索 + 缓存技术（记忆化搜索）

只要我们写出了动态规划写法，就能通过它找到θ了，写一段代码让n从0开始遍历到5000或者差不多的数就好了，然后设置个条件，返回的结果> 0.99999的时候就输出这个数就好了。然后就得到了4451这个答案。
那就好办了，那我直接进行递归并利用缓存技术顺便让n > 4450的时候直接返回1.0即可！
OK，过了。

class Solution:
    def soupServings(self, n: int) -> float:
        if n > 4450:
            return 1.0
        @cache
        def recursion(a_soup: int, b_soup: int) -> float:
            if a_soup <= 0 and b_soup <= 0:
                return 0.5
            elif a_soup <= 0:
                return 1.0
            elif b_soup <= 0:
                return 0.0
            return (recursion(a_soup - 100, b_soup) + recursion(a_soup - 75, b_soup - 25)
                    + recursion(a_soup - 50, b_soup - 50) + recursion(a_soup - 25, b_soup - 75)) / 4
        return recursion(n, n)

---

希望本文章能够帮到您~