【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“136.奇偶数列”的解法探究。先来看一下题目内容：
题目详情
等级：中等
知识点：DP
查看题目：136.奇偶数列 Tom有一个长度为n(1<=n<=100)的数列，数列中只包含1-n且不重复的数字。
这个数列是一个不完整的数列，意思是说数列中有几个位置是空的，Tom想让你帮他把空的位置填上数字，当然是有要求的，对于一个数列来说，如果相邻两位的数字奇偶性不同，这个数列的权值就+1，请你算出来将空位补上以后，权值最小为多少?对于这个数列，空位用0表示。
输入数列长度n(1<=n<=100)和n个数ai(0<=ai<=n)
输出填上空位以后的数列的最小权值。
示例1
输入：
5
[0,5,0,2,3]
输出：
2
注意:
对于样例解释说明，符合题意的数列可以为1 5 4 2 3
解题思路一：贪心算法
对于这道题来说，只需要考虑是奇数还是偶数，而不用理会具体的值。
下面用0代表偶数，1代表奇数，-1表示空位。
这道题对应的空位只有下面5种情况（连续空位的不同个数没有影响）：
1、空位在左右两侧（以左侧举例）-10也就是最边上是连续的空位，然后接一个偶数；
2、空位在左右两侧（以左侧举例）-11也就是最边上是连续的空位，然后接一个奇数；
3、空位在中间，两侧都是奇数1-11；
4、空位在中间，两侧都是偶数0-10；
5、空位在中间，两侧一奇一偶0-11。
计算在5种情况下对应最少可能增加的权值
1、可能增加0(填偶数)或1(偶数不够，要填奇数)
2、可能增加0或1与上面对应
3、可能0(填奇数)或2(奇数不够填偶数)
4、可能0或2与上面对应
5、只能为1
给5种空位重要性排序（确定贪心策略）
第5种，因为不管填什么都增加1，所以排在最后
第3，4种，因为填错了会增加2，比一二种多，所以排第一（相同情况按照空位个数排序，越少越靠前）
第1，2种，排在3，4后面。
计算过程
1、遍历一次，从原数组中提取出这5种空位，同时计算没有填入的奇数偶数分别为多少个
2、按照(3，4)(1，2)(5)分成三组，对前两组按照空位从少到多排序
3、按照贪心策略的顺序
先判断(3，4)中有多少可以增加0的，并消耗掉对应的奇数偶数个数，增加为2的直接跳过，不消耗个数。
然后判断(1，2)中有多少可以增加0的，并消耗掉对应的奇数偶数个数，增加为1的直接跳过，不消耗个数。
最后计算(3，4)剩下的个数*2+(1，2)中剩下的个数*1+(5)中剩下的个数*1
解题思路二：动态规划
样例是0 5 0 2 3，那么两个空位只能填1或者4，所以有1 5 4 2 3和4 5 1 2 3两种情况。
由于前者的权值要小于后者的权值，所以1 5 4 2 3是最优解，如果我们考虑贪心的做法会有很多的情况要讨论，而且也避免不了一些冲突。
我们可以将问题抽象一下，其实就是求对于当前这一个位置之前有多少个奇偶对，可以进一步转换成求前一位的奇偶性，不妨考虑动态规划。
我们设dpi[k]，其中i表示当前所在第i位，j表示前i位一共有j个奇数(那么就有i-j个偶数)，k只能为0或1，当k为0表示第i位放0，k为1表示第i位放1，然后我们同时更新第i位放0和放1的情况的最小值。
那么对于当前的位来说如果填偶数就有dpi[0] = min(dpi-1[0], dpi-1[1] + 1)，如果填奇数就有dpi[1] = min(dpi-1[0] + 1, dpi-1[1])，最终的状态就是min(dpn[1], dpn[0])。
时间复杂度：O(2n^2)
空间复杂度：2n^2+n
看完之后是不是有了答题思路了呢，快来练练手吧：136.奇偶数列
