在講動態規劃題目之前，我先寫一段有關對動態規劃的一些定義，希望能幫助那些沒有瞭解過動態規劃的同學一些基本的知識，這樣能更好的理解程式碼的意圖和背後的思路。
一、定義
動態規劃（Dynamic Programming，DP）是的一個分支，是求解決策過程最佳化的過程。20世紀50年代初，美國數學家貝爾曼（R.Bellman）等人在研究多階段決策過程的優化問題時，提出了著名的最佳化原理，從而創立了動態規劃。
二、思想原理
只要我們能夠把問題看成多階段決策問題皆可以運用動態規劃的思想來解決問題。或者說我們想要求解最優解時，也可以聯想到動態規劃思想。
對於確定性的決策過程。問題中下一段的狀態已由當前段的狀態及決策完全確定。運用動態規劃一個大前提是要所面臨的當前問題只是由前面的決策所決定，並不被後面的決策所影響。還有一點當我們看當問題中的重複子問題時，可以試圖利用動態規劃的思想解題。
三、解題技巧
想要寫出動態規劃問題的程式碼，關鍵有兩個點：
1.能寫出完整的狀態轉移方程
2.能夠解決邊界初始化
爲什麼動態規劃的思想會是的問題比較簡單，因爲我們找到了其中的重疊子問題，然後解決每一個重疊子問題都滿足這一個狀態轉移方程，利用前面已經解決的問題，來解決後面待解決的問題，空間換時間降低了時間複雜度，更重要的時，動態規劃的這一種思想理念是解題的一種好方法。
—————————————————————————————————接下來是題解：
LeetCode： 5 最長迴文子串
題目描述：給定一個字串 s，找到 s 中最長的迴文子串。你可以假設 s 的最大長度爲 1000。
範例1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案。
範例2：
輸入: "cbbd"
輸出: "bb"
先直接上程式碼：（嘗試用動態規劃的思想理解程式碼）
char* longestPalindrome(char* s) {
if (s[0] == 0)
return s;
int i, j, len, max = 0, m, n, k = 0, x;
len = strlen(s);
if (len < 2)
return s;
char* sta = (char*)malloc(sizeof(char) * (len + 1));
int** dp = (int**)malloc(sizeof(int*) * len);
for (i = 0; i < len; i++)
dp[i] = (int*)malloc(sizeof(int) * len);
for (i = 0; i < len; i++)
dp[i][i] = 1;
for (j = 1; j < len; j++)
for (i = 0; i < j; i++)
{
if (s[i] != s[j])
dp[i][j] = 0;
else
{
if (j - i < 3)
dp[i][j] = 1;
else
dp[i][j] = dp[i + 1][j - 1];
}
}
for(i=0;i<len;i++)
for(j=i;j<len;j++)
if (dp[i][j] && j - i + 1 > max)
{
max = j - i + 1;
m = i;
n = j;
}
for (x = m; x <= n; x++)
{
sta[k] = s[x];
k++;
}
sta[k] = 0;
return sta;
}
思路：首先我先明確解題思路。很明顯這是一個求解最優解的問題。最優解就是最長的迴文子串。然後我們構思求解所需要的狀態陣列。我們這裏用的是一個二維狀態陣列dp。
而在這一題中，我們並沒有用一維dp陣列來表示當前的最長迴文子串的長度。我們用的是二維陣列來表示從i->j之間的這段子串是否是迴文子串，我們的狀態是真與假，而不是長度。這一點很重要。
然後明確了狀態陣列所表示的狀態，我們接下來就是要做的是寫出完整的狀態轉移方程。要寫出狀態轉移方程，要我們根據我們明確的狀態來一步一步推導。在推導的開始我們會根據情況的複雜程度來分情況來討論對應的狀態轉移。
首先我們會考慮的存在兩種情況：
s[i]=s[j]時，這時候我們會想到dp[i][j]取決於dp[i+1][j-1];(j>i)
如果s[i]!=s[j]時，那麼很簡單dp[i][j]=false。
那麼這就是大概的一個轉移方程，當然，要寫出完整無誤的狀態轉移方程的話，還要注意其中的小細節。接下來就是邊界的初始化了。
很顯然這裏的主要放生轉移的方程是dp[i][j]=dp[i+1][j-1] 所以容易得出邊界的初始化是dp[i][i]=true;
這裏還有一個值得一提的地方是：
for (j = 1; j < len; j++)
for (i = 0; i < j; i++)
這裏回圈，我一開始習慣性的寫了這個：
for (i = 0; i < len; i++)
for (j = i + 1; j < len; j++)
後來才察覺這樣寫是不行的，下一段的狀態已由當前段的狀態及決策完全確定這一原則，這裏就體現了。