每日leetcode第0080天 1388. Pizza With 3n Slices

这是一道有意思的动态规划题。

首先我们需要做过打家劫舍和打家劫舍2。

我们可以确定的是,你选了一块,这一块相邻的两块就会不见,所以你选的每一块披萨都不允许相邻。

但你如果去用打家劫舍2去做,就会悲剧。

分析一下原因:

打家劫舍2只是不允许打劫相邻的,所以一共打劫的是len / 2家。

但是披萨这道题目只允许我们拿len / 3块。

怎么样可以保证我们拿的并不会过量呢?

但本身的一维数组并没有记录数量,也就是说数据有丢失导致失真。

这个时候我们必须要使用升维,我们需要多记录一个数据,就是已经拿了几块披萨。

total[i][j]表示的是一只到第i块披萨,已经拿了j块披萨,所拿的最大值。

这样一来,我们的状态转移方程式也就出来了。

可以选择拿或者不拿。

不拿:total[i – 1][j]

拿:total[i – 2][j – 1] + s[i – 1]

这里需要考虑一下越界i为1的时候会越界,所以i为1要单独考虑做预处理。

因为要重复算两次,所以我们就写成一个函数来找最大值。

从两个最大值中找较大的输出。

 

以898611举例,我们先算89861最大值16。再算98611最大值15。

 



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。