假设我们有一个称为nums的数字列表,其中每个值都确定完成任务所需的时间单位。我们可以跳过任何非连续任务,我们必须找到完成所有任务所需的最短时间。
因此,如果输入类似于nums = [11、6、8、16],则输出将为14,因为我们可以跳过第一个和最后一个任务。
为了解决这个问题,我们将按照以下步骤操作:
n:= nums的大小
table:=做一个nx2矩阵,用0填充
table[0,0]:= 0
table [0,1]:= nums [0]
对于范围在1到n-1之间的i
table [i,0]:= table [i-1,1]
table [i,1] =(table [i-1,0]和table [i-1] [1]的最小值)+ nums [i]
返回表格行的最小值[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