在Python中找到完成所有任务所需的最短时间的程序
假设我们有一个名为nums的数字列表,其中每个值都确定完成任务所需的时间单位。我们可以跳过任何非连续的任务,我们必须找到完成所有任务所需的最短时间。
因此,如果输入是nums = [11、6、8、16],则输出将为14,因为我们可以跳过第一个和最后一个任务。
为了解决这个问题,我们将按照以下步骤进行:
- n := nums的大小
- table:=制作n x 2矩阵,并用0填充
- table [0,0]:= 0
- table [0,1]:= nums [0]
- 对于i在1到n-1的范围内,执行以下操作
- table [i,0]:= table [i-1,1]
- table [i,1] =(table [i-1,0]和table [i-1]的最小值)+ nums [i]
- 返回table行[n-1]的最小值
让我们看一下以下实现来更好地理解:
示例
class Solution:
def solve(self, nums):
n = len(nums)
table = [[0] * 2 for _ in range(n)]
table[0][0] = 0
table[0][1] = nums[0]
for i in range(1, n):
table[i][0] = table[i - 1][1]
table[i][1] = min(table[i - 1][0], table[i - 1][1]) + nums[i]
return min(table[n - 1])
ob = Solution()
nums = [11, 6, 8, 16]
print(ob.solve(nums))
输入
[11、6、8、16]
输出
14