动态规划:对一组数字进行分区的方法多种

Question

在阅读算法书时，我发现了以下练习。

给定一组 n 个元素，编写一个算法来查找 分区方式。 示例：当 n = 2 时，有 2 种方法可以将集合(分为 两个集合与一个元素，或进入原始集合和空集合(。

我没有使用算法，而是尝试使用动态编程的python代码。

def ways(n):
dp = [0]*(n+1), 
sum = [0]*(n+1) ## declaring 2 arrays of n+1 size
dp[0] = 0
dp[1] = 1
sum[0] = 0
sum[1] = 1
lastcalc = 1     # last calculated var
for i in range (2,n):
if lastcalc < i/2 : 
for j in range (lastcalc, i/2):
sum[j] = sum[j-1] + dp[j]
lastcalc = (i/2) # update the lastcalculated variable
dp[i] = sum[i/2]
return dp[n]
print(ways(2))

但是，代码不起作用并给了我一个错误。

类型错误："元组"对象不支持项分配

我的问题：我该如何解决这个问题？我可以说这段代码应用了动态编程吗？

Answer 1

您在dp声明的末尾有一个逗号。这使它成为一个元组，而不是一个列表，并且元组不可修改。删除它，这是一个错字。