Python程序：查找最小和子序列（至少选择连续三个元素中的一个）

Python 服务器端编程编程

假设我们有一个名为nums的数字列表，我们需要从给定列表中找到一个最小和子序列，条件是必须至少选择所有连续三个数字组中的一个数字。如果给定列表的长度小于3，则仍然应该选择一个数字。

例如，如果输入为nums = [2, 3, 4, 5, 6, 7]，则输出为7，因为我们可以选择2和5。

为了解决这个问题，我们将遵循以下步骤：

n := nums的长度
如果n等于0，则
- 返回0
如果n等于1，则
- 返回nums[0]
如果n等于2，则
- 返回nums[0]和nums[1]中的最小值
table := 一个长度为n的列表，并用0填充
table[0] := nums[0]
table[1] := nums[1]
table[2] := nums[2]
对于从3到n的i，执行：
- table[i] := nums[i] + table[i - 3]，table[i - 2]和table[i - 1]中的最小值
res := table[n - 1]，table[n - 2]和table[n - 3]中的最小值
返回res

让我们看看下面的实现来更好地理解。

示例代码

在线演示

class Solution:
   def solve(self, nums):
      n = len(nums)
      if n == 0:
         return 0
      if n == 1:
         return nums[0]
      if n == 2:
         return min(nums[0], nums[1])
      table = [0] * n

      table[0] = nums[0]
      table[1] = nums[1]
      table[2] = nums[2]

      for i in range(3, n):
         table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])

         res = min(table[n - 1], table[n - 2], table[n - 3])
      return res

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

输入

[2, 3, 4, 5, 6, 7]

输出

Arnab Chakraborty

更新于：2020年11月25日

807 次浏览

启动您的职业生涯

完成课程获得认证

开始学习