【線上程式設計産品介紹】
阿裡雲開發者社群線上程式設計：
免費刷題大神器，助你拿到好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.奇偶數列