python 一道动态规划的问题i

python 一道动态规划的问题i

题目是这样的：

给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个非连续子序列，使其和最大，输出最大子序列的和。
这里非连续子序列的定义是，子序列中任意相邻的两个数在原序列里都不相邻。
例如，对于L=[2,-3,3,50]， 输出52（分析：很明显，该列表最大非连续子序列为[2,50]).

我的思路是利用动态规划，设opt[i]表示有i个数的时候的非连续子列，对于opt（i），存在两种情况，选择序列L中的第i个数，由于是非连续子列，那么opt[i]=opt[i-2]+L[i],还要一种就是不选择L[i],那么opt[i]=opt[i-1],然后比较二者的大小，将较大的赋值给opt[i],
而递归的出口为opt[0]=L[0],opt[1]=max(L[0],L[1])
因此，代码如下

max_length = len(L)
if max_length<2:
    opt[0]=L[0]
else:
    opt = [0]*max_length      # 定义一个和L一样大小的列表
    opt[0]=L[0]               
    opt[1]=max(L[0],L[1])
    for i in range(2,max_length):
        opt[i]=max(opt[i-2]+L[i],opt[i-1])    # 递归条件
    print(opt[-1])                 # opt列表的最后一个值就是最大值

我变换了几个L的例子，结果都显示正确，但是OJ却没有通过，发现，对于这个例子
L=[-1,-2,3]，最大值应该是3，而我计算的却是2

回答：

    for i in range(2,max_length):
        opt[i]=max(opt[i-2]+L[i],opt[i-1],L[i])    # 递归条件

每一个元素都有自己独立作为一个子序列，或者开始一个子序列的可能。

以上是 python 一道动态规划的问题i 的全部内容， 来源链接： utcz.com/a/162643.html

回到顶部