【概率与统计动态规划】 808. 分汤

本文主要是介绍【概率与统计动态规划】 808. 分汤，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

C++动态规划
数学概率与统计

LeetCode 808. 分汤

有 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。返回值在正确答案 10-5 的范围内将被认为是正确的。
示例 1:
输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
示例 2:
输入: n = 100
输出: 0.71875
提示:
0 <= n <= 10⁹

动态规划

当n较小时，通过动态规划求解。当n 较大时结果大于0.99999,忽略误差后就是1。
由于都是25倍数，所有n = n/25+(0 != n%25)

动态规划的状态表示

dp[i][j] 表示i单位的汤A，j单位的汤B 的概率。
空间复杂度：O(nn)

状态规划的状态表示

每种状态分别枚举4种可能并除以4。

动态规划的初始值

dp[0][0] = 0.5。

动态规划的填表顺序

i，j从小到。每种分配 A汤一定变少。

动态规划的翻转

dp[n][n]

注意：

n可以为0。

代码

核心代码

class Solution {
public:double soupServings(int n) {n = (n+24)/25;if (n > 1000) { return 1; }vector<vector<double>> dp(n + 1, vector<double>(n + 1,0.5));	for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {double sum = 0;for (int k = 4; k >= 1; k--){const int i1 = max(0, i - k);const int i2 = max(0, j - (4 - k));if ((0 == i1) && (0 == i2)) { sum += 0.5; }else if (0 == i1) {sum += 1;}else if (0 == i2) {}else {sum += dp[i1][i2];}					}dp[i][j] = sum / 4;}}return dp.back().back();}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1,  double t2)
{auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{int n;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){n = 50;auto res = Solution().soupServings(n);AssertEx(0.62500, res);}TEST_METHOD(TestMethod01){n = 100;auto res = Solution().soupServings(n);AssertEx(0.71875, res);}TEST_METHOD(TestMethod02){n = 1;auto res = Solution().soupServings(n);AssertEx(0.62500, res);}TEST_METHOD(TestMethod03){n = 2;auto res = Solution().soupServings(n);AssertEx(0.62500, res);}TEST_METHOD(TestMethod04){n =3;auto res = Solution().soupServings(n);AssertEx(0.62500, res);}TEST_METHOD(TestMethod05){n = 4;auto res = Solution().soupServings(n);AssertEx(0.62500, res);}TEST_METHOD(TestMethod06){n = 5;auto res = Solution().soupServings(n);AssertEx(0.62500, res);}TEST_METHOD(TestMethod07){n = 0;auto res = Solution().soupServings(n);AssertEx(0.5, res);}};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛