回答思路

简单的思路是递归，给定序列[a_0, a_1, a_2, ..., a_k]，假设新数列前i-1个数值已经构建好了，那么我们要决策是下一个数值i要不要改成1，还是保留原值 那么就变成了比较[b_0, b_1, b_{i-1}, a_i, con(剩下的a, a_i)] 和 [b_0, b_1, b_{i-1}, 1, con(剩下的a, 1)] 所以我们可以用递归的思路来完成 def con(x, previous_number=None): # 输入是原始序列的话，那么最左边的比较对象设为自己就好 # 这样可以保证不会对要不要改成1的结果有所影响 if previous_number is None: previous_number = x[0] k = len(x) if k == 1: # 只剩一个元素了，那就比较下是保留原值好 # 还是变成1比较好 if abs(1 - previous_number) > abs(x[0] - previous_number): x[0] = 1 v = abs(x[0] - previous_number) else: # 有多个元素 # 算一下保留原值带来的增益是多少 x1_remning, v1_remning = con(x[1:], x[0]) v1 = abs(x[0] - previous_number) + v1_remning # 算一下改为1带来的增益是多少 x2_remning, v2_remning = con(x[1:], 1) v2 = abs(1 - previous_number) + v2_remning # 改为1有利可图，把当前子数列的第一个元素改为1 # 然后接着往后判断 if v1 < v2: v = v2 x[0] = 1 x_remning = x2_remning else: v = v1 x_remning = x1_remning # 拼接上后面的数列元素，这里也是已经调优过的 x = [x[0]] + x_remning return x, v # 定义一个算增益的函数 def value(x): v = 0 for i in range(1, len(x)): v += abs(x[i] - x[i - 1]) return v # 构造一个数列来说明，并不是直接间隔变为1是好的策略 x = [8, 9, 5, 3, 1, 4, 7, 2, 6] print('Before: ', x) x, v = con(x) print('After: ', x, value(x)) x1 = [8, 1, 5, 1, 1, 1, 7, 1, 6] x2 = [1, 9, 1, 3, 1, 4, 1, 2, 1] print('Comparison: ', x1, value(x1)) print('Comparison: ', x2, value(x2)) 输入结果为： Before: [8, 9, 5, 3, 1, 4, 7, 2, 6] After: [1, 9, 1, 3, 1, 4, 7, 1, 6] 37 Comparison: [8, 1, 5, 1, 1, 1, 7, 1, 6] 32 Comparison: [1, 9, 1, 3, 1, 4, 1, 2, 1] 28 这里可以看到最佳结果[1, 9, 1, 3, 1, 4, 7, 1, 6]并不完全是间隔取1的。