Python程序:通过删除数字找到最大可添加分数
假设我们有一个数字列表称为nums。 让我们考虑一个操作,可以选择一个数字,然后删除它并通过数字及其相邻两个数字的总和增加我们的分数。 只要我们不选择列表中的第一个或最后一个数字,我们就可以随意执行此操作。 我们必须找到可能的最大分数。
因此,如果输入是nums=[2, 3, 4, 5, 6],那么输出将是39,因为我们可以选择5,然后总和将为(4+5 +6)=15,数组将为[2, 3, 4, 6],然后选择4,因此总和为(3+4+6)= 13,并且数组将是[2,3,6],选择3,总和将是(2+3+6)=11,因此总和为15+13+11=39
要解决这个问题,我们将按以下步骤执行 –
- n:=num_s的大小
- 如果n<3,则:
- 定义一个大小为(n + 1)x(n + 1)的二维数组
- 初始化len := 3,当len<= n时,更新(增加len)-
- 初始化i := 1,当i + len – 1<= n时,更新(i增加1)-
- r:=i+len -1
- ans:=0
- 初始化k: =i +1,当 k <r -1时,更新(增加k)-
- curr:=dp[i,k]+ dp[k,r]+ nums[k-1]
- 如果curr>ans,则:
- ans:=ans + nums[i-1]+ nums[r-1]
- dp[i,r] :=ans
- 初始化i := 1,当i + len – 1<= n时,更新(i增加1)-
- 返回dp [1, n]
让我们看下面的实现以更好地理解
更多Python相关文章,请阅读:Python 教程