LeetCode 799. 香槟塔(DP动态规划)

文章目录
1. 题目2. 解题

1. 题目

我们把玻璃杯摆成金字塔的形状,其中第一层有1个玻璃杯,第二层有2个,依次类推到第100层,每个玻璃杯(250ml)将盛有香槟。

从顶层的第一个玻璃杯开始倾倒一些香槟,当顶层的杯子满了,任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。
当左右两边的杯子也满了,就会等流量的流向它们左右两边的杯子,依次类推。(当最底层的玻璃杯满了,香槟会流到地板上)

例如,在倾倒一杯香槟后,最顶层的玻璃杯满了。倾倒了两杯香槟后,第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后,第二层的香槟满了 – 此时总共有三个满的玻璃杯。在倒第四杯后,第三层中间的玻璃杯盛放了一半的香槟,他两边的玻璃杯各自盛放了四分之一的香槟,如下图所示。

LeetCode 799. 香槟塔(DP动态规划)

现在当倾倒了非负整数杯香槟后,返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例(i 和 j都从0开始)。

示例 1:
输入: poured(倾倒香槟总杯数) = 1,
query_glass(杯子的位置数) = 1,
query_row(行数) = 1
输出: 0.0
解释: 我们在顶层(下标是(0,0))倒了一杯香槟后,
没有溢出,因此所有在顶层以下的玻璃杯都是空的。

示例 2:
输入: poured(倾倒香槟总杯数) = 2,
query_glass(杯子的位置数) = 1,
query_row(行数) = 1
输出: 0.5
解释: 我们在顶层(下标是(0,0)倒了两杯香槟后,
有一杯量的香槟将从顶层溢出,
位于(1,0)的玻璃杯和(1,1)的玻璃杯平分了这一杯香槟,
所以每个玻璃杯有一半的香槟。

注意:
poured 的范围[0, 10 ^ 9]。
query_glass 和query_row 的范围 [0, 99]。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/champagne-tower
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
public:
double champagneTower(int poured, int query_row, int query_glass) {
vector<vector<double>> dp(101, vector<double>(101, 0.0));
double up_l, up_r;
dp[0][0] = poured;
for(int i = 1; i <= query_row; ++i)
{
for(int j = 0; j <= i; ++j)
{
up_l = j > 0 ? dp[i-1][j-1] : 0;//上层左侧酒量
up_r = dp[i-1][j];//上层右侧酒量
dp[i][j] += up_l > 1 ? (up_l-1)/2.0 : 0;
//自己需要留下一杯 -1, 不够的话得到 0
dp[i][j] += up_r > 1 ? (up_r-1)/2.0 : 0;
//自己需要留下一杯 -1, 不够的话得到 0
}
}
return min(1.0, dp[query_row][query_glass]);
}
};

24 ms 41.6 MB

祝大家国庆节中秋节快乐!


我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
LeetCode 799. 香槟塔(DP动态规划)

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

LeetCode 799. 香槟塔(DP动态规划)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » LeetCode 799. 香槟塔(DP动态规划)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏