网易2017年合唱团
做题经验：
对于一个复杂的题，若是附加条件太多，不能一步到位的解决，可以逐渐的减少附加条件，也就是逐渐的减少参数，等有思路了，再把参数添加进去。
对于这题，作者就是这么想的，一开始，把附加条件d去掉，就是一个很典型的DP问题，然后建模， 递归实现，DP算法实现，最后再把d添加进去。
一、递归实现
这里需要提醒的是，因为能力值有正有负，在下一个值不知道正负性的情况下，是不能确定应该返回哪一个值的，很可能这一次的最小值乘以负数就变成最大值了。
因此不是每次返回一个值，而是每次返回两个值。一个最大值，一个最小值。
import sys
n = 36
ability = [7,-15,31,49,-44,35,44,-47,-23,15,-11,10,-21,10,-13,0,-20,-36,22,-13,-39,-39,-31,-13,-27,-43,-6,40,5,-47,35,-8,24,-31,-24,-1]
k,d = 2, 31
def chorus(n, ability, k):
if k == 1:
return [max(ability),min(ability)]
if k == n:
result = 1
for i in range(n):
result = result * ability[i]
return [result,result]
#选中最后一个同学，会得到最大值与最小值
last_list = chorus(n-1,ability[0:n-1],k-1)
#未选中最后一个同学，得到最大值与最小值
no_last_list = chorus(n-1,ability[0:n-1],k)
#不能认为，index为0的就是max，因为ability[-1]的不确定性，所以可能会不断改变
#因此需要再每一步都判断一下，得到最大或最小值
return [max(last_list[0]*ability[-1],
last_list[1]*ability[-1],
max(no_last_list)),
min(last_list[0] * ability[-1],
last_list[1] * ability[-1],
min(no_last_list))]
print(chorus(n, ability, k))
二、DP实现（不加d）
这里因为只有两个参数，n和k，分析状态转移方程，可以知道，k一定时，f[k][n_id]的每个状态都可以由k-1的每个状态决定，因此这里只需要维护两个一维数组即可。
代码实现：
n = 36
ability = [7,-15,31,49,-44,35,44,-47,-23,15,-11,10,-21,10,-13,0,-20,-36,22,-13,-39,-39,-31,-13,-27,-43,-6,40,5,-47,35,-8,24,-31,-24,-1]
k,d = 3, 31
def chorus(n, ability, k):
pre_res_max = []
pre_res_min = []
if k == 1:
return max(ability)
else:
for i in range(n):
pre_res_max.append(max(ability[0:i+1]))
pre_res_min.append(min(ability[0:i+1]))
for k_id in range(2,k+1):
after_res_max = []
after_res_min = []
for n_id in range(n):
if k_id > n_id:
res = 1
for i in range(n_id+1):
res = res * ability[i]
after_res_max.append(res)
after_res_min.append(res)
else:
#对于这一点尤其要注意，用哪个元素，千万不能错了。
#这里要是用n_id，就是49*49了，元素就重复了。
max1 = pre_res_max[n_id-1]*ability[n_id]
min1 = pre_res_min[n_id-1] * ability[n_id]
max2 = after_res_max[n_id-1]
min2 = after_res_min[n_id-1]
result_list = [max1,max2,min1,min2]
after_res_max.append(max(result_list))
after_res_min.append(min(result_list))
pre_res_max = after_res_max
pre_res_min = after_res_min
return max(pre_res_max)
print(chorus(n, ability, k))
三、DP实现（加d）
因为这里有三个参数n,k,d，需要好好定义一下需要保存的数组。
f[k][i]代表的是，选择k个学生并且以第i个学生作为结尾时的最大（或最小）乘积。
如何定义需要保存的数组，也是一门玄学？
基本上，是根据动态转移方程中的参数的值，来确定需要保存的东西。
比如国王与金矿问题中，下一行的某个状态，由上一行的某两个状态决定，因为需要维护一个一维数组，用来保存上一行的最优值。
然而在LeetCode第62题中，因为状态转移方程是dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，当前状态由上一行的第j列与当前行的前一个决定，所以只需要保存两个数据即可。
要根据状态转移方程确定需要保存的东西。
因此在k等于1时，初始化数组时，需要注意初始化的正确性。
建模分析
根据f[k][i]的定义，我们可以得到最优子结构与状态转移方程。
一定要举例说明
-
1、例如f[3][6]，已经选择第7个同学作为结尾，那么ability的第7个值就作为乘积，若是前一个同学选择第6个，那么就是f[2][5] * ability[6]，这是其中一个最优子结构，同理，若是倒数第二个同学是第5个，那么就是f[2][4] * ability[6]。
-
2、理论上，对于n_id，有n_id-1个子结构。因此应该在range(0,n_id)中遍历每个序号作为倒数第二个同学，在遍历的就结果中选择最大最小值。
-
3、又因为这里加了限制，倒数第二个同学的编号与最后一个编号不能超过d。
于是，修改循环的取值，若n_id大于d，则从0开始，小于d就从 n_id - d开始
改为range(max(0, n_id - d), n_id)。
这里真的是根据题意得到的一个小技巧。
代码实现：
n = int(input())
ability = [int(x) for x in input().split()]
k, d = [int(x) for x in input().split()]
def chorus_dp2(n,ability,k,d):
# 初始化两个数组，分别存储最大值最小值
# 其中，f[k][i]代表的是，选择k个学生并且以第i个学生作为结尾时的最大（或最小）乘积
f_max = []
f_min = []
for k_id in range(k):
f_max.append([])
f_min.append([])
for n_id in range(n):
if k_id == 0:
#在k等于1 的时候，根据f[k][i]的定义可知，第i个值就应该是ability[i]
f_max[k_id].append(ability[n_id])
f_min[k_id].append(ability[n_id])
else:
f_max[k_id].append(0)
f_min[k_id].append(0)
for k_id in range(1,k):
res_mid_max = []
res_mid_min = []
for j in range(max(0, n_id - d), n_id):
res_mid_max.append(max(f_max[k_id-1][j] * ability[n_id],
f_min[k_id-1][j] * ability[n_id]))
res_mid_min.append(min(f_max[k_id-1][j] * ability[n_id],
f_min[k_id-1][j] * ability[n_id]))
f_max[k_id][n_id] = max(res_mid_max)
f_min[k_id][n_id] = min(res_mid_min)
return f_max
print(max(chorus_dp2(n,ability,k,d)[k-1]))
#这段代码并没有考虑k等于n的情况。有bug。
#题目中也没有给k大于n时应该怎么办，是不是允许重复的。题目这一点也出的不好。
网友评论