題目：用戶上傳若干個(gè) adapter index 序列，這些序列是由 “A”、“T”、“C”、“G” 四種字母組成的字符串，長(zhǎng)度可能是6、8、16。然后指定一個(gè)數(shù)字 n，需要輸出 count 組的 adapter index 的組合，每組中必須有 n 個(gè)adapter index，且使這些組合中，每一位的四種字母占比要盡量均勻，而且都在 12.5%-60% 之間，優(yōu)先滿足前 count 個(gè)分組，最終不足 n 個(gè)或者不滿足占比的要舍棄。如果最后輸出這樣一組 adapte indexr：

ACTGCAG
TGAAGCT
GCATTAG
GATGATG

那么第一位的 A 占比為 25%，T占比25%，G占比50%，C占比0%；第二位的 A 占比25%，T占比0%， G占比25%，C占比50%......依次計(jì)算。

由題目可知，我們最終想要的結(jié)果是一些字符串的分組，這個(gè)問(wèn)題就非常類似動(dòng)態(tài)規(guī)劃里的背包問(wèn)題或者是股票問(wèn)題。

背包問(wèn)題中，我們要找的是把物品放入限制容量的背包的最大價(jià)值，需要從從若干個(gè)物品中挑選，本問(wèn)題也可以看成是從若干個(gè)字符串中挑選出最符合要求的（即 ATCG 最均勻的），所以對(duì)于單個(gè)分組，我們可以使用動(dòng)態(tài)規(guī)劃，來(lái)求得最佳的組合。問(wèn)題中也提到，可以優(yōu)先滿足前幾個(gè)組，之后不滿足就可以舍棄，我們就可以使用遞歸，先滿足第一組，然后再在剩下的 adapter 中繼續(xù)挑選滿足要求的最佳組合。

先來(lái)構(gòu)建動(dòng)態(tài)規(guī)劃的框架。

動(dòng)態(tài)規(guī)劃中，我們第一步先要找出狀態(tài)和選擇。

在這個(gè)問(wèn)題中，我們要做的是遍歷所有的 adapter，然后判斷把當(dāng)前 adapter 加入到數(shù)組中時(shí)，是否為“最佳”的情況。

狀態(tài)有兩種：數(shù)組中 adapter 的數(shù)量、可選擇的 adapter。

選擇：當(dāng)前的 adapter 是否進(jìn)入數(shù)組。

找到狀態(tài)和選擇之后，動(dòng)態(tài)規(guī)劃的問(wèn)題基本就可以解決了，有一個(gè)動(dòng)態(tài)規(guī)劃的框架：

for 狀態(tài)1 in 狀態(tài)1的所有取值
      for 狀態(tài)2 in 狀態(tài)2的所有取值
          for ...
              dp[狀態(tài)1][狀態(tài)2][...] = 擇優(yōu)（選擇1，選擇2....）

第二步要明確 dp 數(shù)組的定義

dp 數(shù)組是什么？其實(shí)就是描述局部問(wèn)題的一個(gè)數(shù)組，剛才提到的“狀態(tài)”，現(xiàn)在就要用 dp 數(shù)組把狀態(tài)表示出來(lái)。

我們的狀態(tài)有兩個(gè)，所以我們就需要一個(gè)二維數(shù)組，一維表示可選擇的 adapter，一維表示當(dāng)前數(shù)組中已有的 adapter 的數(shù)量。

dp[i][w]的定義如下：對(duì)于前 i 個(gè)adapter，當(dāng)前數(shù)組中的 adapter 數(shù)量為 w，這種情況下當(dāng)前數(shù)組的最優(yōu)均勻程度為 dp[i][w]。

注：題目中的最優(yōu)解，我們可以理解為最均勻，所以這里的最優(yōu)情況即為最均勻程度。

如果 dp[3][5] = 6，其含義就是對(duì)于給定的所有 adapter ，如果只對(duì)前 3 個(gè) adapter 進(jìn)行選擇，當(dāng)數(shù)組中有 5 個(gè)adapter 時(shí)，最均勻程度就為 6。

設(shè) adapter 總數(shù)為 N 個(gè)，數(shù)組的容量為 W。

根據(jù)這個(gè)定義，我們想求的最佳答案就是 dp[N][W]。

還要記得處理 base case，這個(gè)問(wèn)題的 base case 就是 dp[0][..] 和 dp[..][0]，因?yàn)楫?dāng)沒(méi)有可選 adapter 或者數(shù)組容量為 0 時(shí)，均勻程度無(wú)法計(jì)算。

如此，細(xì)化動(dòng)態(tài)規(guī)劃的框架：

      for i in count(indexes):
          for w in [1...8]
              dp[i][w] = max(
                  把當(dāng)前 index 放入結(jié)果集，      
                  不把當(dāng)前 index 放入結(jié)果集
              )
       return dp[count(indexes)][8];
         

根據(jù)“選擇”，思考狀態(tài)轉(zhuǎn)移的邏輯

簡(jiǎn)單來(lái)說(shuō)，就是上面的把“把當(dāng)前 index 放入結(jié)果集” 和 “不把當(dāng)前 index 放入結(jié)果集” 如何用代碼體現(xiàn)呢？

前面提到，對(duì)于前 i 個(gè)adapter，當(dāng)前數(shù)組中的 adapter 數(shù)量為 w，這種情況下當(dāng)前數(shù)組的最優(yōu)均勻程度為 dp[i][w]**。

如果沒(méi)有把第 i 個(gè) adapter 放入數(shù)組，那么最均勻程度 dp[i][w] 就應(yīng)該等于 dp[i-1][w]，繼承之前的結(jié)果。

如果把第 i 個(gè) adapter 放入了數(shù)組，那么最均勻程度 dp[i][w] 就應(yīng)該是在dp[i-1][w-1] 的基礎(chǔ)上進(jìn)行計(jì)算，當(dāng)數(shù)組新添加了一個(gè)元素 ，就應(yīng)該計(jì)算新元素加入之后的分值。

既然我們最后要輸出的是一個(gè)數(shù)組，所以還需要一個(gè)數(shù)組來(lái)記錄數(shù)組中的 adapter。

細(xì)化一下代碼：

private function filtrateAdapters($indexes, $count)
{
        // 初始化數(shù)組
        $adapters = [];
        $indexesLen = count($indexes);

        // 放入第一個(gè) index
        $adapters[0][0] = [];
        $percent[0][0] = -100000;

        // 動(dòng)態(tài)規(guī)劃
        for ($i = 0; $i <= $indexesLen; $i ++) {
            for ($w = 0; $w <= $count; $w ++) {
                // 初始化的一部分，分值初始化為0，數(shù)組初始化為空數(shù)組
                if ($i == 0 || $w == 0) {
                    $percent[$i][$w] = 0;   
                    $adapters[$i][$w] = [];
                    continue;
                }
                // 判斷最優(yōu)
                // 放入的情況
                $adapters[$i][$w] = array_merge($adapters[$i-1][$w-1], [$indexes[$i]]);

                $baseBank = $this->baseRank($adapters[$i][$w]);
                $percent[$i][$w] = $this->percentageScore($baseBank);

                // 不放的情況
                if ($percent[$i][$w] < $percent[$i-1][$w] && $percent[$i-1][$w] != 0) {
                    // 出棧
                     //dd($adapters[$i][$w], $adapters[$i-1][$w-1], $percent[$i][$w], $percent[$i-1][$w-1]);
                    $adapters[$i][$w] = $adapters[$i-1][$w];
                    $percent[$i][$w] = $percent[$i - 1][$w];
                }
            }
        }
        return $adapters[$indexesLen][$count];
}

這里我們需要一個(gè)計(jì)算“均勻程度”的方法，這里就不再貼出來(lái)了，就是簡(jiǎn)單地每一位計(jì)算一下。

然后我們需要用遞歸的方法來(lái)求出最終的若干個(gè)數(shù)組，整理出代碼：

    private function filtrateAdapters(&$indexes, $count, &$res=[])
    {
        // 初始化數(shù)組
        $result = [];
        $adapters = [];
        $indexesLen = count($indexes);

        $adapters[0][0] = [];
        $percent[0][0] = -100000;

        // 動(dòng)態(tài)規(guī)劃
        for ($i = 0; $i <= $indexesLen; $i ++) {
            for ($w = 0; $w <= $count; $w ++) {

                // 初始化的一部分，分值初始化為0，數(shù)組初始化為空數(shù)組
                if ($i == 0 || $w == 0) {
                    $percent[$i][$w] = 0;
                    $adapters[$i][$w] = [];
                    continue;
                }

                // 判斷最優(yōu)
                // 放入的情況
                $adapters[$i][$w] = array_merge($adapters[$i-1][$w-1], [$indexes[$i]]);

                $baseBank = $this->baseRank($adapters[$i][$w]);
                $percent[$i][$w] = $this->percentageScore($baseBank);

                // 不放的情況
                if ($percent[$i][$w] < $percent[$i-1][$w] && $percent[$i-1][$w] != 0) {
                    $adapters[$i][$w] = $adapters[$i - 1][$w];
                    $percent[$i][$w] = $percent[$i - 1][$w];
                }
            }
        }

        // 最后判斷結(jié)果，如果是負(fù)值，代表結(jié)束
        if (count($adapters[$indexesLen][$count]) < $count || $percent[$indexesLen][$count] < 0) {
            //dd($res);
            return $res;
        }

        // 判斷是否超出界限
        $baseBank = $this->repository->baseRank($adapters[$indexesLen][$count]);
        foreach ($baseBank as $item) {
            foreach ($item as $value) {
                $p = str_replace("%", '', $value);
                if ($p > 60 || $p < 12.5) {
                    return $res;
                }
            }
        }

        $res[] = [
            'adapters' => $adapters[$indexesLen][$count],
            'percent' => $this->repository->baseRank($adapters[$indexesLen][$count])
        ];

        // 然后從原indexes數(shù)組中去除已選的元素，繼續(xù)下一輪
        $newIndexes = array_diff($indexes, $adapters[$indexesLen][$count]);
        $this->filtrateAdapters($newIndexes, $count, $res);
    }

    // 根據(jù)占比來(lái)計(jì)算分值
    private function percentageScore($baseBank)
    {
        // 如果超出界限，則返回-1，其他情況計(jì)算平均值

        /**
         * 結(jié)構(gòu)：
         * a=>[0:10%,1:10%...]
         * t=>[0:10%,1:10%...]
         * c=>[0:10%,1:10%...]
         * g=>[0:10%,1:10%...]
         */

        $score = 0;
        foreach ($baseBank as $item) {
            foreach ($item as $value) {
                $p = str_replace("%", '', $value);

                if ($p > 60 || $p < 12.5) {
                    $score += -1;
                }

                if ($p > 25) {
                    $score +=  (60-$p)/35 * 100;
                } elseif ($p <= 25) {
                    $score +=  ($p-12.5)/12.5 * 100;
                }
            }
        }

        return $score;
    }