一、簡(jiǎn)介

動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的過(guò)程。20世紀(jì)50年代初，美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃的應(yīng)用極其廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事以及自動(dòng)化控制等領(lǐng)域，并在背包問(wèn)題、生產(chǎn)經(jīng)營(yíng)問(wèn)題、資金管理問(wèn)題、資源分配問(wèn)題、最短路徑問(wèn)題和復(fù)雜系統(tǒng)可靠性問(wèn)題等中取得了顯著的效果。

雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題，但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過(guò)程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。

在現(xiàn)實(shí)生活中，有一類活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。因此各個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線．這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為多階段決策過(guò)程，這種問(wèn)題稱為多階段決策問(wèn)題。在多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，稱這種解決多階段決策最優(yōu)化的過(guò)程為動(dòng)態(tài)規(guī)劃方法

動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解這類問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子問(wèn)題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。

以一個(gè)例子來(lái)說(shuō)明動(dòng)態(tài)規(guī)劃的概念(leetcode第5題最長(zhǎng)回文子串)：

給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

在這個(gè)例子中，一個(gè)字符串如果是回文子串，那么去掉頭尾也照樣是回文子串。而每一個(gè)字符都有可能是最長(zhǎng)回文子串的一部分。

二、基本概念

1. 多階段決策問(wèn)題

   如果一類活動(dòng)過(guò)程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需作出決策（采取措施），一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過(guò)程的活動(dòng)路線，則稱它為多階段決策問(wèn)題
   各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對(duì)應(yīng)于一個(gè)策略可以確定活動(dòng)的效果，這個(gè)效果可以用數(shù)量來(lái)確定。策略不同，效果也不同，多階段決策問(wèn)題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果

2. 狀態(tài)

   狀態(tài)表示每個(gè)階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在上面的例子中狀態(tài)就是某個(gè)子串是否是回文串。

3. 無(wú)后效性

   我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了。換句話說(shuō)，過(guò)程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是這個(gè)子串是否是回文串，一旦確定了這個(gè)子串的狀態(tài)，在這個(gè)子串基礎(chǔ)上的更長(zhǎng)的字符串不受這階段之前各段狀態(tài)的影響。狀態(tài)的這個(gè)性質(zhì)意味著過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展，這個(gè)性質(zhì)稱為無(wú)后效性。

4. 狀態(tài)轉(zhuǎn)移方程

   給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關(guān)系看成(x(k)，u(k))與x(k+1)確定的對(duì)應(yīng)關(guān)系，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。上面的例子中狀態(tài)轉(zhuǎn)移方程是：P(i,j)=P(i+1,j?1)∧(Si==Sj)。一個(gè)子串的狀態(tài)依賴于去掉頭尾之后的狀態(tài)以及頭尾的狀態(tài)。只有去掉頭尾之后是回文串并且頭尾的字符相同時(shí)，這個(gè)子串才是一個(gè)回文串。

三、示例

上面這個(gè)例子使用一個(gè)二維數(shù)組表示各個(gè)階段的狀態(tài)，這個(gè)二維數(shù)組的行是子串的起始位置，列是子串的結(jié)束位置。由于j>=i，所以只需要考慮二維數(shù)組的主對(duì)角線的上半部分，對(duì)角線上的值永遠(yuǎn)是true。用true表示這個(gè)子串是回文串，false不是回文串。那么對(duì)于某個(gè)固定位置的數(shù)組元素來(lái)說(shuō)，它的值依賴于左下角的元素的值。進(jìn)行填充的時(shí)候只能一列一列地進(jìn)行填充，同一列的元素從上到下依次填充。

給定一個(gè)字符串s="abcba"

	0	1	2	3	4
0	true	false	false	false	true
1		true	false	true	false
2			true	false	false
3				true	false
4					true

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        // 特判
        if (len < 2){
            return s;
        }
        //最大長(zhǎng)度初始是1
        int maxLen = 1;
        int begin  = 0;

        // 1. 狀態(tài)定義
        // dp[i][j] 表示s[i...j] 是否是回文串


        // 2. 初始化
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        char[] chars = s.toCharArray();
        // 3. 狀態(tài)轉(zhuǎn)移
        // 注意：先填左下角
        // 填表規(guī)則：先一列一列的填寫，再一行一行的填，保證左下方的單元格先進(jìn)行計(jì)算
        for (int j = 1;j < len;j++){
            for (int i = 0; i < j; i++) {
                // 頭尾字符不相等，不是回文串
                if (chars[i] != chars[j]){
                    dp[i][j] = false;
                }else {
                    // 相等的情況下
                    // 考慮頭尾去掉以后沒(méi)有字符剩余，或者剩下一個(gè)字符的時(shí)候，肯定是回文串
                    if (j - i < 3){
                        dp[i][j] = true;
                    }
                    //否則，判斷其左下角的元素的狀態(tài)
                    else {
                        // 狀態(tài)轉(zhuǎn)移
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要dp[i][j] == true 成立，表示s[i...j] 是否是回文串
                // 此時(shí)更新記錄回文長(zhǎng)度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        // 4. 返回值
        return s.substring(begin,begin + maxLen);
    }
}