動(dòng)態(tài)規(guī)劃（Dynamic programming，簡(jiǎn)稱 DP）是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法。

動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。

動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單。大致上，若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題），再根據(jù)子問(wèn)題的解以得出原問(wèn)題的解。

通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次，從而減少計(jì)算量：一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出，則將其記憶化存儲(chǔ)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表。這種做法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用。

嚴(yán)格意義上，動(dòng)態(tài)規(guī)劃只能用來(lái)解決最優(yōu)化問(wèn)題，但在OI中，計(jì)數(shù)等非最優(yōu)化問(wèn)題的遞推解法也常被不規(guī)范地稱作 DP。事實(shí)上，動(dòng)態(tài)規(guī)劃與其它類型的遞推的確有很多相似之處，學(xué)習(xí)時(shí)可以注意它們之間的異同。

一、簡(jiǎn)介

動(dòng)態(tài)規(guī)劃算法是五種常見(jiàn)的算法之一，通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(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ì)算了很多次。

動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題，動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑、一種方法，而不是一種特殊算法。它往往是針對(duì)一種最優(yōu)化問(wèn)題，由于各種問(wèn)題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同的問(wèn)題，有各具特色的解題方法，而不存在一種萬(wàn)能的動(dòng)態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問(wèn)題。

二、適用條件

任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。，適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足最優(yōu)化原理和無(wú)后效性。

最優(yōu)化原理，即最優(yōu)子結(jié)構(gòu)性質(zhì)，最優(yōu)化原理可這樣闡述:一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問(wèn)題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

無(wú)后效性，將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策，而只能通過(guò)當(dāng)前的這個(gè)狀態(tài)。換句話說(shuō)，每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)。這就是無(wú)后向性，又稱為無(wú)后效性。

動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)時(shí)間復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過(guò)程中，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。

三、動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)

動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)主要有兩種方法：

（1）自頂向下（又稱記憶化搜索、備忘錄）：基本上對(duì)應(yīng)著遞歸函數(shù)實(shí)現(xiàn)，從大范圍開(kāi)始計(jì)算，要注意不斷保存中間結(jié)果，避免重復(fù)計(jì)算

（2）自底向上（遞推）：從小范圍遞推計(jì)算到大范圍

四、經(jīng)典例題

動(dòng)態(tài)規(guī)劃在編程中常用解決最長(zhǎng)公共子序列問(wèn)題、矩陣連乘問(wèn)題、凸多邊形最優(yōu)三角剖分問(wèn)題、電路布線等問(wèn)題。

例題一：最長(zhǎng)公共子序列問(wèn)題（求LCS具體是什么）

給出兩個(gè)字符串A B，求A與B的最長(zhǎng)公共子序列（子序列不要求是連續(xù)的）。

比如兩個(gè)串為：abcicba 和 abdkscab，則 ab是兩個(gè)串的子序列，abc也是，abca也是，其中abca是這兩個(gè)字符串最長(zhǎng)的子序列。

Input

第1行：字符串A 

第2行：字符串B 

(A,B的長(zhǎng)度 <= 1000)

Output

輸出最長(zhǎng)的子序列，如果有多個(gè)，隨意輸出1個(gè)。

Sample Input

abcicba
abdkscab

Sample Output

abca

思路：此題的切入點(diǎn)就是動(dòng)態(tài)規(guī)劃，通過(guò)動(dòng)歸來(lái)確定哪些字符是最長(zhǎng)公共子序列中的字符，mat[i][j] 表示第一個(gè)序列的前i個(gè)字符和第二個(gè)序列的前j個(gè)字符的公共子序列，動(dòng)態(tài)轉(zhuǎn)移方程為：

 dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1] + (A[i]==B[j] ? 1 : 0))，表示在這三種狀態(tài)中取到最大值，

（1）第一種狀態(tài)表示不錄入第一個(gè)序列的第i個(gè)字符時(shí)的最長(zhǎng)公共子序列，

（2）第二種狀態(tài)表示不錄入第二個(gè)序列的第j個(gè)字符時(shí)的最長(zhǎng)公共子序列，

（3）第三種狀態(tài)表示第一個(gè)序列的前i-1個(gè)字符與第二個(gè)序列前j-1個(gè)字符的公共子序列加上最后一個(gè)字符的錄入狀態(tài)，如果最后的一個(gè)字符相等則錄入狀態(tài)為1，否則為0。

然后根據(jù)動(dòng)歸的狀態(tài)，來(lái)判斷我們要求得的序列中的字符有哪些。

代碼如下：

#include<queue>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
 
using namespace std;
 
char a[1001], b[1001];
int dp[1001][1001], len1, len2;
 
void lcs(int i, int j)
{
    for(i=1; i<=len1; i++)
    {
        for(j=1; j<=len2; j++)
        {
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else if(dp[i-1][j] > dp[i][j-1])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = dp[i][j-1];
        }
    }
}
 
void llcs()
{
    int i, j, z = 0;
    char c[1001];
    memset(c, 0, sizeof(c));
    i = len1, j = len2;
    while(i!=0 && j!=0)
    {
        if(a[i-1] == b[j-1])
        {
            c[z++] = a[--i];
            j--;
        }
        else if(dp[i-1][j] < dp[i][j-1])
            j--;
        else if(dp[i][j-1] <= dp[i-1][j])
            i--;
    }
    for(i=z-1; i>=0; i--)
        printf("%c", c[i]);
    printf("\n");
 
}
 
int main()
{
    while(~scanf(" %s", a))
    {
        scanf(" %s", b);
        memset(dp, 0, sizeof(dp));
        len1 = strlen(a);
        len2 = strlen(b);
        lcs(len1, len2);
        llcs();
    }
    return 0;
}

例題二：爬樓梯

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個(gè)正整數(shù)。

示例 1：

輸入： 2

輸出： 2

解釋： 有兩種方法可以爬到樓頂。

          （1） 階 + 1 階

          （2）階

示例 2：

輸入： 3

輸出： 3

解釋： 有三種方法可以爬到樓頂。

          （3）1 階 + 1 階 + 1 階

          （4）1 階 + 2 階

          （5）2 階 + 1 階

思路：

爬樓梯算是DP的經(jīng)典題目，遞歸+記憶化，也就是遞推，我們需要定義好狀態(tài)，還有狀態(tài)的轉(zhuǎn)移方程。最后爬的步數(shù)還是得看之前的，即依賴之前的步驟。

1. 反著考慮，有幾種方案到第i階樓梯，答案是2種：

第i-1階樓梯經(jīng)過(guò)一步

第i-2階樓梯經(jīng)過(guò)兩步

假設(shè)count(i)表示到第i階樓梯方案的個(gè)數(shù)，則count(i) = count(i-1) + count(i-2)

第一階是1種，第二階是2種。代碼如下：

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = [1,2]   #一次就只能走這兩步
        for i in range(2,n):
            count.append(count[i-1]+count[i-2])	#不停地把后面的臺(tái)階的結(jié)束放到count里面
        return count[n-1]

這里是O(n!)

2. 我們想到可以轉(zhuǎn)化為fibonaqi問(wèn)題。假設(shè)一共有10階樓梯，每步可以爬1步或者2步，那么你爬到10階一共有兩種方法，從8階爬2步，或從9階爬1步，那么爬到9階也是這樣，那這就是一共基本的斐波那契數(shù)列。

dp[i] = dp[i-1] + dp[i-2]

i-1的時(shí)候跳一步可以到達(dá)i

i-2的時(shí)候跳一步是i-1，這個(gè)變成dp[i-1]的子問(wèn)題了,直接跳兩步可以到達(dá)i

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1 for i in range(n+1)]   #狀態(tài)的定義
        for i in range(2,n+1):
            dp[i] = dp[i-1]+dp[i-2]	#狀態(tài)轉(zhuǎn)移方程
        return dp[n]

這里應(yīng)該是O(n)

3. 還有一種更快速的，列表初始化好，然后再用fibonaqi數(shù)列轉(zhuǎn)移方程。

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        condition = [0]*(n+1)		#牛逼的初始化列表
        condition[0] = 1
        condition[1] = 1
        for i in range(2,n+1):
            condition[i] = condition[i-1]+condition[i-2]   #依然還是狀態(tài)轉(zhuǎn)移fibonaqo
        return condition[n]

這里列表初始化只用來(lái)O(1)，最后復(fù)雜度為O(n)。