再開一個新坑，以後會不定期總結一下對于一些基本算法題的解法思路和實作。作為一個AI領域的從業者，不僅對于AI本身的技術要有掌握，對于計算機科學中的基本算法思想也要紮實的基礎，這樣才能做一個合格的算法工程，本人在這方面的能力還不夠成熟，是以開這個坑，希望通過這種方式，真正去了解算法的本質。
本文要總結的題目是找最長回文子串，對應leetcode中的題目如下：
Longest Palindromic Substring
Given a string
s , find the longest palindromic substring in s . You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd" Output: "bb"
本文主要集中在如何一步一步使用動态規劃的方法來解決這個問題并進行優化的過程，有其他更好的解決該問題的方法不在本文中讨論。
最簡單思想
首先，這個題目最簡單的思想就是暴力周遊所有可能結果，假設目前字元串序列為
具體做法是周遊所有可能長度的子串，判斷其是不是回文子串，然後記錄其長度，最後傳回那個長度最長的子串即可。
暴力搜尋的問題
暴力搜尋的時間效率肯定是最低的，那麼低在哪裡呢？我們以
為例，列舉暴力搜尋的前幾個步驟，很明顯就能看出來問題：
- 子串長度為1時，周遊所有單個字元 ，此時所有單個字元都是回文。
中判斷回文的代碼_（基礎算法複習）之最長回文子串的動态規劃解法 - 子串長度為2時，周遊所有二進制字元子串 ，然後判斷每個元素是否為回文，判斷依據是
中判斷回文的代碼_（基礎算法複習）之最長回文子串的動态規劃解法 中判斷回文的代碼_（基礎算法複習）之最長回文子串的動态規劃解法 - 子串長度為3時，周遊所有三元字元串 ，這裡判斷每個元素是否為回文。
中判斷回文的代碼_（基礎算法複習）之最長回文子串的動态規劃解法 - 子串長度為4時，周遊所有四元字元串 ，然後判斷每個元素是否為回文。
中判斷回文的代碼_（基礎算法複習）之最長回文子串的動态規劃解法 - 重複上述步驟，直到周遊到 這個長度為n的字元串為止。
中判斷回文的代碼_（基礎算法複習）之最長回文子串的動态規劃解法
進一步分析，其實步驟3時，其實會用到1的結果，因為每個元素中間項
通過1已經知道是回文了，那麼隻要判斷
是否成立就行了。然而步驟3是重複處理了。
同樣的，步驟4同樣用到了步驟2的結果，對于
，如果知道
是回文，那麼隻要分析
就可以了。是以步驟4也重複處理。
引入動态規劃
通過上面的分析可以知道，暴力搜尋時，并不是每一個元素都需要去專門周遊并判斷是否為回文，有些元素可以通過曆史的結果來幫助判斷一個元素是否為回文。同時我們也可以總結一些規律：
假設
是我們要求解的最長的回文子串(其中j>=i)，那麼它必然符合兩個條件：
a.
b.
（j>=i+2）必然也是一個回文子串，否則上述假設不成立。
基于上述規律，我們可以将這個問題進行拆分，分成最基本的優化目标問題單元：即隻要到一個回文子串，然後以該子串為中心，左右兩邊的字元若相等，則找到一個更長的新的回文子串。即從一進制字元開始，以該字元為中心向兩邊擴充的方式，逐漸找到更長的回文子串，有點像穿衣服一樣，一層一層往上套。這個就是動态規劃的思想，當然我隻是用口語化的方式描述了一下，理論化的動态規劃肯定更加嚴謹公式化，但是我就不在這裡讨論了，有興趣的可以自行查閱。
那麼如何實作上述的思想呢？前面說了，我要知道
是否為回文，那麼主要是需要知道
是否為回文。這裡可以将其視作一個填表問題。我們設計一個bool型的n*n的二維矩陣A，如果
是一個回文串，那麼
位置就填上true，否則為false。填表的順序則是從長度為1的字元串開始，逐級向長度更長的字元串填，間而言之就是一種周期性的斜向上方向，具體如圖：
其實上圖也說明了一個事情，就是我們并不需要把所有表格都填上，而是隻需要填滿上三角的表格就能得到最終結果。是以，在代碼實作的時候，我們可以初始化一個上三角形狀的二維數組，這樣可以節省一半的空間。（代碼實作的時候，我還是初始化了整矩陣，為了與後續優化區分）。
我們要做的，就是當遇到回文串時，不僅在上述表格相應位置填上值，而且需要記錄目前子串的起始位置和長度，用于後續的傳回結果。
代碼實作1
下面給出我寫的初步動态規劃解法，隻列出關鍵邏輯，完整代碼後續會放到github上，到時會貼出來。代碼不是很優美，求大佬輕噴。
int s_size = s.size();
vector<vector<bool> > result(s_size, vector<bool> (s_size,false));
初始化一個n*n的bool型矩陣，n為字元串長度。
for(int i=0;i<s_size;i++)
{
result[i][i] = true;
if(i < s_size-1)
{
if (s[i]==s[i+1])
{
result[i][i+1] = true;
cur_max = 2;
start = i;
}
}
}
這裡是先填充對角線，以及
上斜線的位置，對角線對應一進制字元，這個很好了解，都是回文，而上斜線的位置也很好處理，隻要判斷
就可以了。同時要記錄目前最長回文的起始位置start以及長度cur_max。
for (int distance = 2;distance < s_size;distance++)
{
// cout<<distance;
for (int i = 0;i+distance<s_size;i++)
{
result[i][i+distance] = (result[i+1][i+distance-1]&&(s[i]==s[i+distance]));
if(result[i][i+distance])
{
if(distance+1>cur_max)
{
cur_max = distance+1;
start = i;
end = i+distance;
}
}
}
}
這裡最外層的循環表示字元串的長度周遊，裡層周遊則是對字元串起始位置的周遊。循環内部的邏輯在上面章節已經介紹過，即根據
是否為回文以及
來判斷
是否為回文。同時記錄回文子串的起始位置和長度。
進一步優化
上述代碼在leetcode運作後的時間和空間成本如下：
可以看到無論是時間成本還是空間成本都是很高的，優化的空間很大呀！
回頭看我們的上述解法過程，我們将一個矩陣中一個斜線上的所有位置填表稱為一個epoch操作。每輪epoch其實都隐含得使用了前一個epoch的資訊，更加具體的說是前一個epoch的某一個位置上的值。我們是否需要一整個二維矩陣表格來填某個epoch的資訊呢？答案是不需要！具體原因看下圖圖示：
具體來說，每次填表格，其實隻需要其右下角的表格的值就可以了，而初始的對角線和上斜線位置的判斷也是很簡單就能實作也不用記錄，是以實際上我們不用一個二維矩陣，隻需要幾個臨時變量記錄右下角的表格值就可以了。
另外，我們需要變更填表的順序，之前我們的順序都是每個epoch斜上方向45度填。這裡我們改換成如下的填表順序：
其中箭頭上标的數字代表循環的epoch輪數。即每次我向左斜向上方填表，填到邊界時，跳到下一輪的其實位置，接着填。
優化代碼實作
代碼的話其實注意幾個點就行，一個是每一輪周遊的順序是往左斜向上的，另一個就是每一輪要記錄目前輪起始的位置，因為下一輪的起始位置是與前一輪的起始位置和目前輪數相關的，如圖：
主要代碼邏輯如下：
bool pre_flag = false;
int epoch_start_i = 0;
int epoch_start_j = 0;
這裡直接初始化一個臨時變量存放右下角的值，然後初始化兩個位置變量來存每一個epoch的起始位置。
對于對角線和上斜線的處理就不貼出來了，這裡貼一下其他位置的填法：
//根據右下角的表格填目前表格
pre_flag = (pre_flag && s[i]==s[j]);
//如果是回文，且長度最長，則記錄起始位置
if(pre_flag && j-i+1>cur_max)
{
cur_max = j-i+1;
start = i;
}
//到邊界位置，需要換到下一輪的起始位置
if(i-1<0 || j+1 >=s_size)
{
//本輪起始位置為對角線上
if (epoch_start_i == epoch_start_j)
{
i =epoch_start_i;
j = epoch_start_j+1;
}else
{
//本輪起始位置在上斜線上
i =epoch_start_i+1;
j = epoch_start_j;
}
continue;
}else
{
//向左斜上方向處理
i--;
j++;
continue;
}
最後，上述代碼在leetcode上運作的花費如下：
可以看到，無論是時間複雜度，還是空間複雜度，都有了很大的優化。