动态规划_实战2

网易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)。
这里真的是根据题意得到的一个小技巧。