LeetCode 分汤（动态规划+记忆搜索）

65 阅读 0 评论 43 点赞

我是靠谱客的博主欢喜黑裤，最近开发中收集的这篇文章主要介绍LeetCode 分汤（动态规划+记忆搜索），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

有 A 和 B 两种类型的汤。一开始每种类型的汤有 N 毫升。有四种分配操作：

提供 100ml 的汤A 和 0ml 的汤B。
提供 75ml 的汤A 和 25ml 的汤B。
提供 50ml 的汤A 和 50ml 的汤B。
提供 25ml 的汤A 和 75ml 的汤B。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为0.25的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意不存在先分配100 ml汤B的操作。

需要返回的值：汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。

示例:

输入: N = 50
输出: 0.625
解释:
如果我们选择前两个操作，A将首先变为空。对于第三个操作，A和B会同时变为空。对于第四个操作，B将首先变为空。
所以A变为空的总概率加上A和B同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

注意:

0 <= N <= 10^9。
返回值误差在 10^-6 的范围将被认为是正确的。

$思路分析：$ 这道题还是有点难度的，首先我们需要将N缩小一些。

第一，四种分发基数都是25，即如果不足25按照25继续分，那么我们可以将N缩小为原来的25分之一。

第二，N的范围是[0, 10⁹]，这是一个特别大的数字了。并且提示中注明当我们返回的结果与真实误差小于10^-6的时候，就算正确。而当N趋向于无穷大时，A先被分完以及A和B同时被分完的概率会无限接近于1。经过严格计算我们知道当N >= 4800之后，返回的概率值与1的差距就小于10^-6了。所以当N >= 4800的时候，我们就直接返回1。

第三，动态数组dp[i][j]表示:当给定i毫升的A和j毫升的B，汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2
转移方程：dp[i][j] = 0.25 * (dp[i-100][j] + dp[i-75][j-25] + dp[i-50][j-50] + dp[i-75][j-25])
将N缩小为原来的25分之一的转移方程：dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-3][j-1])

class Solution {
public:
    double soupServings(int N) {
        if (N >= 4800){//N超过了4800，结果与1分厂接近
            return 1;
        }
        int myN = (int)ceil(N / 25.0);//缩小为原来的25分之一
        //dp[i][j]表示:当给定i毫升的A和j毫升的B，汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2
        vector<vector<double>> dp(myN + 1, vector<double>(myN + 1, 0));
        dp[0][0] = 0.5;//特殊情况，0毫升A、0毫升B（同时分配完 1 * 0.5）
        for (int i = 1; i < myN + 1; ++i){
            dp[i][0] = 0;//i毫升A，0毫升B，则B必定先分配完，不可能出现A先分配完或者A、B同时分配完
            dp[0][i] = 1;//0毫升A，i毫升B，则A必定先分配完，概率为1
        }
        //开始动态规划
        for (int i = 1; i < myN + 1; ++i){
            int a1 = i - 4 > 0 ? i - 4 : 0;//不足4，按4算（实际上是不足100，按100算，然后分配完了，没有剩余）
        	int a2 = i - 3 > 0 ? i - 3 : 0;//不足3，按3算（实际上是不足75，按75算，然后分配完了，没有剩余）
        	int a3 = i - 2 > 0 ? i - 2 : 0;//不足2，按2算（实际上是不足50，按75算，然后分配完了，没有剩余）
        	int a4 = i - 1 > 0 ? i - 1 : 0;//不足1，按1算（实际上是不足25，按25算，然后分配完了，没有剩余）
        	for(int j = 1; j < myN + 1; ++j) {
        		int b1 = j;
        		int b2 = j - 1 > 0 ? j - 1 : 0;//不足1，按1算（实际上是不足25，按25算，然后分配完了，没有剩余）
        		int b3 = j - 2 > 0 ? j - 2 : 0;//不足2，按2算（实际上是不足50，按75算，然后分配完了，没有剩余）
        		int b4 = j - 3 > 0 ? j - 3 : 0;//不足3，按3算（实际上是不足75，按75算，然后分配完了，没有剩余）
                //状态转移方程：dp[i][j] = 0.25 * (dp[i-100][j] + dp[i-75][j-25] + dp[i-50][j-50] + dp[i-75][j-25])
                //将N缩小为原来的25分之一的转移方程：dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-3][j-1])
        		dp[i][j]= 0.25 * (dp[a1][b1] + dp[a2][b2] + dp[a3][b3] + dp[a4][b4]);
        	}
        }
        return dp[myN][myN];
    }
};

在这里插入图片描述
当然也可以使用带备忘录的搜索算法。（有点像斐波拉契而数列）

class Solution {
public:
    double soupServings(int N) {
        if (N >= 4800){//N超过了4800，结果与1分厂接近
            return 1;
        }
        int myN = (int)ceil(N / 25.0);//缩小为原来的25分之一
        map<pair<int, int>, double> hashMap;//用于记录{a，b}的概率结果
        return func(hashMap, myN, myN);
    }
    double func(map<pair<int, int>, double> &hashMap, int a, int b){
        if (a <= 0 && b <= 0){//A.B同时分配完
            return 0.5;
        }
        else if (a <= 0){//A先分配完
            return 1;
        }
        else if (b <= 0){//B先分配完
            return 0;
        }
        else if (hashMap.count({a, b})){//如果这个状态已经搜索过了
            return hashMap[{a, b}];
        }
        else{
            hashMap[{a, b}] = 0.25*(func(hashMap, a - 4, b) + func(hashMap, a - 3, b - 1) + func(hashMap, a - 2, b - 2) + func(hashMap, a - 1, b - 3));
        return hashMap[{a, b}];
        }
    }
};