題目：用戶上傳若干個(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è)問題就非常類似動(dòng)態(tài)規(guī)劃里的背包問題或者是股票問題共缕。
背包問題中，我們要找的是把物品放入限制容量的背包的最大價(jià)值士复，需要從從若干個(gè)物品中挑選图谷，本問題也可以看成是從若干個(gè)字符串中挑選出最符合要求的（即 ATCG 最均勻的），所以對(duì)于單個(gè)分組阱洪，我們可以使用動(dòng)態(tài)規(guī)劃便贵，來求得最佳的組合。問題中也提到冗荸，可以優(yōu)先滿足前幾個(gè)組承璃，之后不滿足就可以舍棄，我們就可以使用遞歸蚌本，先滿足第一組盔粹，然后再在剩下的 adapter 中繼續(xù)挑選滿足要求的最佳組合。
先來構(gòu)建動(dòng)態(tài)規(guī)劃的框架程癌。
動(dòng)態(tài)規(guī)劃中舷嗡，我們第一步先要找出狀態(tài)和選擇。
在這個(gè)問題中嵌莉，我們要做的是遍歷所有的 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ī)劃的問題基本就可以解決了扰肌，有一個(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í)就是描述局部問題的一個(gè)數(shù)組曙旭，剛才提到的“狀態(tài)”盗舰，現(xiàn)在就要用 dp 數(shù)組把狀態(tà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è)問題的 base case 就是 dp[0][..] 和 dp[..][0]霜定，因?yàn)楫?dāng)沒有可選 adapter 或者數(shù)組容量為 0 時(shí)，均勻程度無法計(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)單來說磨德，就是上面的把“把當(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]**啦吧。
如果沒有把第 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ù)組來記錄數(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ì)算“均勻程度”的方法和橙，這里就不再貼出來了仔燕，就是簡(jiǎn)單地每一位計(jì)算一下造垛。
然后我們需要用遞歸的方法來求出最終的若干個(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ù)占比來計(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;
}
