动态规划是一种非常精妙的算法思想，它没有固定的写法、极其灵活，常常需要具体问题具体分析。

动态规划(Dynamic Programming, DP)是一种用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划会将每个求解过的子问题的解记录下来，这样当下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算。

一般可以使用递归或者递推的写法来实现动态规划，其中递归写法在此处又称作记忆化搜索。

先来讲解递归写法。通过这部分内容的学习，读者应能理解动态规划是如何记录子问题的解，来避免下次遇到相同的子问题时的重复计算的。

以斐波那契(Fibonacci)数列为例：

    int F(int n)
    {
        if(n == 0 || n == 1) return 1;
        else return F(n-1) + F(n-2);
    }

在计算过程中，递归式会涉及到很多重复的计算。事实上，由于没有及时保存中间计算的结果，实际复杂度会高达O(2n次方)，即每次都会计算F(n-1)和F(n-2)这两个分支，基本不能承受n较大的情况。

为了避免重复计算，可以开一个一维数组dp，用以保存已经计算过的结果，其中dp[n]记录F(n)的结果，并用dp[n]=-1表示F(n)当前还没有被计算过。

然后就可以在递归当中判断dp[n]是否是-1：如果不是-1，说明已经计算过F(n)，直接返回dp[n]就是结果；否则，按照递归式进行递归。代码如下：

    int F(int n)
    {
        if(n == 0 || n == 1) return 1;      // 递归边界
        if(dp[n] != -1) return dp[n];       // 已经计算过，直接返回结果
        else{
            dp[n] = F(n-1) + F(n-2);
            return dp[n];
        }
    }

通过已计划搜索，可以将复杂度从O(2n次方)降到O(n)。

通过上面的例子可以引申出一个概念： 如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题(Overlapping Subproblems)。动态规划通过记录重叠子间题的解，来使下次碰到相同的子问题时直接使用之前记录的结果，以此避免大量重复计算。因此，一个问题必须拥有重叠子问题，才能使用动态规划去解决。

以经典的数塔问题为例，将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字……第n层有n个数字。现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加后得到的和最大是多少？

注意到：如果要求出“从位置（1，1）到达最底层的最大和dp[1][1]”，那么一定要先求出它的两个子问题“从位置（2，1）到达最底层的最大和dp[2][1]”和“从位置（2，2）到达最底层的最大和dp[2][2]”，即进行了一次决策，写成式子就是：

dp[1][1] = max(dp[2][1], dp[2][2]) + f[1][1]

由此可以归纳得到：如果要求出dp[i][j]，那么一定先求出两个子问题：“从位置（i+1, j）到达最底层的最大和dp[i+1][j]”和“从位置（i+1, j+1）到达最底层的最大和dp[i+1][j+1]”，携程式子就是：

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

把dp[i][j] 称为问题的状态，而把上面的式子称作状态转移方程，它把状态dp[i][j]转移为dp[i+1][j]和dp[i+1][j+1]。可以发现，数塔的最后一层的dp值总是等于元素本身，即dp[n][j] ＝ f[n][j] (1≤n)，把这种可以直接确定其结果的部分称为边界，而动态规划的递推写法总是从这些边界出发，通过状态转移方程扩散到整个dp数组。

下面根据这种思想写出动态规划的代码：

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int maxn = 1000;
    int f[maxn][maxn], dp[maxn][maxn];

    int main()
    {
        int n;
        scanf_s("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                scanf_s("%d%d", &f[i][j]);      // 输入数塔
            }
        }

        // 边界
        for(int j = 1; j <= n; j++)
        {
            dp[n][j] = f[n][j];
        }

        // 从n-1层不断往上计算出dp[i][j]
        for(int i = n-1; i>= 1; i--)
        {
            for(int j = 1; j <= i; j++)
            {
                // 状态转移方程
                d[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j];
            }
        }
        printf("%d\n", dp[1][1]);
        return 0;
    }

显然，使用递归也可以实现上面的例子（即从dp[1][1]开始递归，直至到达边界时返回结果）。两者的区别在于：使用递推写法的计算方式是自底向上(Bottom-up Approach)，即从边界开始，不断向上解决问题，直到解决了目标问题；而使用递归写法的计算方式是自顶向下(Top-down Approach)，即从目标问题开始，将它分解成子问题的组合，直到分解至边界为止。

通过上面的例子再引申出一个概念：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构(Optimal Substructure)。最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导而来。因此，一个问题必须拥有最优子结构，才能使用动态规划去解决。

需要指出，一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。下面指出这两个概念的区别：

1. 分治与动态规划。分治和动态规划都是将问题分解为子问题，然后合并子问题的解得到原问题的解。但是不同的是，分治法分解出的子问题是不重叠的，因此分治法解决的问题不拥有重叠子问题，而动态规划解决的问题拥有重叠子问题。

2. 贪心与动态规划。贪心和动态规划都要求原问题必须拥有最优子结构。二者的区别在于，贪心法采用的计算方式类似于上面介绍的“自顶向下”，但是并不等待子问题求解完毕后再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题就不去求解了，直接抛弃。

最大连续子序列和问题如下：给定一个数字序列A1，A2，...，An，求i，j(1≤i≤j≤n)，使得Ai+...+Aj最大，输出这个最大和。

如果使用暴力解法，枚举左端点和右端点需要O(n平方)的复杂度，计算A[i]+...+A[j]需要O(n)的复杂度，因此总复杂度为O(n立方)。采用记录前缀和的方法使计算的时间变为O(1)，总复杂度仍然为O(n平方)。

通过动态规划算法，复杂度可降为O(n)。并且可以发现左端点的枚举是没有必要的。

1. 步骤1：令状态dp[i]表示以A[i]作为末尾的连续序列的最大和（这里是说A[i]必须作为连续序列的末尾）。通过设置数组dp，则最终结果要求的最大和其实就是dp[0],dp[1],dp[2],..., dp[n-1]中的最大值。

2. 步骤2：因为dp[i]要求是必须以A[i]结尾的连续序列，那么只有两种情况：

   1. 这个最大和的连续序列只有一个元素，即以A[i]开始，以A[i]结尾。

   2. 这个最大和的连续序列有多个元素，即从前面某处A[p]开始，一直到A[i]结尾。

   由于只有两种情况，于是状态转移方程为：dp[i]=max{A[i],dp[i-1]+A[i]}，这个式子只与i和i之前的元素有关，且边界为dp][0]=A[0]，由此从小到大枚举i，即可得到整个dp数组。

    #include<cstdio>
    #include <algorithm>
    using namespace std;
    const int maxn = 10010;
    int A[maxn], dp[maxn];      // A[i]存放序列，dp[i]存放以A[i]结尾的连续序列的最大和
    int main() 
    {
        int n;
        scanf_s("%d", &n);
        for(int i = 0; i < n; i++)
        {
            scanf_s("%d", &A[i]);
        }
        // 边界
        dp[0] = A[0];
        for(int i = 1; i < n; i++)
        {
            // 状态转移方程
            dp[i] = max(A[i], dp[i-1]+A[i]);
        }

        // dp[i]存放以A[i]结尾的连续序列的最大和，需要遍历i得到最大的才是结果
        int k = 0;
        for(int i = 1; i < n; i++)
        {
            if(dp[i] > dp[k])
            {
                k = i;
            }
        }
        printf("%d", dp[k]);
    }

状态的无后效性是指：当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。

此必须设计一个拥有无后效性的状态以及相应的状态转移方程，否则动态规划就没有办法得到正确结果。

最长不下降子序列(Longest Increasing Sequence, LIS)是这样一个问题：在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。

可以用最原始的办法来枚举每种情况，即对千每个元素有取和不取两种选择，然后判断序列是否为不下降序列。如果是不下降序列，则更新最大长度，直到枚举完所有情况并得到最大长度。由于需要对每个元素都选择取或者不取，那么如果元素有n个，时间复杂度将高达O(2的n次方)。

采用动态规划方法，令dp[i]表示以A[i]结尾的最长不下降子序列长度，则对A[i]来说有两种可能：

1. 如果存在A[i]之前的元素A[j]，使得A[j]≤A[i]且dp[j]+1>dp[i]（即把A[i]在以A[j]结尾的LIS后面时能比当前以A[i]结尾的LIS长度更长），那么就把A[i]跟在以A[j]结尾的LIS后面，形成一条更长的不下降子序列（令dp[i]=dp[j]+1）。

2. 如果A[i]之前的元素都比A[i]大，那么A[i]就只好自己形成一条LIS，但是长度为1，即这个子序列里面只有一个A[i]。

状态转移方程：dp[i]=max{1,dp[j]+1}(j=1,2,...,i-1&&A[j]<A[i])

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int N = 100;
    int A[N], dp[N];
    int main() 
    {
        int n;
        scanf_s("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf_s("%d", &A[i]);
        }

        int ans = -1;       // 记录最大的dp[i]
        for(int i = 1; i <= n; i++)
        {
            // 按顺序计算出dp[i]的值
            dp[i] = 1;  // 边界初始条件
            for(int j = 1; j < i; j++)
            {
                if(A[i] >= A[j] && (dp[j]+1 > dp[i]))
                {
                    dp[i] = dp[j] + 1;
                }
            }
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }

最长公共子序列(Longest Common Subsequence, LCS) 的问题描述为：给定两个字符串（或数字序列）A和B，求二个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）。

暴力解法：设字符串A和B的长度分别是n和m ，那么对两个字符串中的每个字符，分别有选与不选两个决策，而得到两个子序列后，比较两个子序列是否相同又需要O(max(m,n))，这样总复杂度就会达到O(2的m+n次方 x max(m,n))，无法承受数据大的情况。

动态规划方法：令dp[i][j]表示字符串A的i号位和字符串B的j号位之前跌的LCS长度（下表从1开始），那么可以根据A[i]和B[j]的情况，分为两种策略：

1. 若A[i] == B[j]，则字符串A与字符串B的LCS增加1，即有dp[i][j]=dp[i-1][j-1]+1。

2. 若A[i] != B[j]，则字符串Ai号位和字符串B的j号位之前的LCS无法延长，因此dp[i][j]将会继承dp[i-1][j]和dp[i][j-1]中的较大值，即有dp[i][j]=max{dp[i-1][j],dp[i][j-1]};

可得到状态转移方程：当A[i] == B[j]时，dp[i][j]=dp[i-1][j-1]+1；当A[i] != B[j]时，dp[i][j]=max{dp[i-1][j],dp[i][j-1]}，边界：dp[i][0]=dp[0][j]=0。

    #include <cstdio>
    #include <string>
    #include <algorithm>
    using namespace std;
    const int N = 100;
    char A[N], B[N];
    int dp[N][N];
    int main()
    {
        int n;
        gets(A + 1);    // 从下标为1开始读入
        gets(B + 1);
        int lenA = strlen(A+1);
        int lenB = strlen(B+1);
        // 边界
        for(int i = 0; i <=lenA; i++)
        {
            dp[i][0] = 0;
        }
        for(int j = 0; j <=lenB; j++)
        {
            dp[0][j] = 0;
        }

        // 状态转移方程
        for(int i = 1; i <= lenA; i++)
        {
            for(int j = 1; j <= lenB; j++)
            {
                if(A[i] == B[j])
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // dp[lenA][lenB]就是答案
        printf("%d\n", dp[lenA][lenB]);
    }

最长回文子串的问题描：给出一个字符串S，求S的最长回文子串的长度。

暴力解法：枚举子串的两个端点i和j，判断在[i, j]区间内的子串是否回文。从复杂度上来看，枚举端点需要O(n的2次方)，判断回文需要O(n)，因此总复杂度是O(n的3次方)。

动态规划方法：令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。这样根据S[i]是否等于S[j]，可以把转移情况分为两类：

1. 若S[i]==S[j]，那么只要S[i+1]至S[j-1]是回文子串，S[i]至S[j]就是回文子串；如果S[i+1]至S[j-1]不是回文子串，S[i]至S[j]也不是回文子串。

2. 若S[i]!=S[j]，那么S[i]至S[j]一定不是回文子串。

则状态转移方程：当S[i]==S[j]时，dp[i][j]=dp[i+1][j-1]；当S[i]!=S[j]时，dp[i][j]=0；边界：dp[i][i]=1，dp[i][i+1]=(S[i]==S[i+1]) ? 1 : 0。

    #include <cstdio>
    #include <string>
    using namespace std;
    char S[maxn];
    int dp[maxn][maxn];
    int main()
    {
        gets(S);
        int len = strlen(S), ans = 1;
        memset(dp, 0, sizeof(dp));

        // 边界
        for(int i = 0; i < len; i++)
        {
            dp[i][i] = 1;
            if(i < len - 1)
            {
                if(S[i] == S[i+1])
                {
                    dp[i][i+1] = 1;
                    ans = 2;
                }
            }
        }

        // 状态转移方程
        for(int L = 3; L <= len; L++)
        {
            for(int i = 0; i + L -1 < len; i++)
            {
                int j = i + L -1;
                if(S[i] == S[j] && dp[i+1][j-1] == 1)
                {
                    dp[i][j] = 1;
                    ans = L;
                }
            }
        }
        printf("%d\n", ans);
    }

DAG就是有向无环图。求解DAG最长路和最短路的思想是一致的，因此下面以最长路为例。本节着重解决两个问题：1.求整个DAG中的最长路径（即不固定起点跟终点）。2.固定终点，求DAG的最长路径。

先讨论第一个问题：给定一个有向无环图，怎样求解整个图的所有路径中权值之和最大的那条。针对这个问题，令dp[i]表示从i号顶点出发能获得的最长路径长度，这样所有dp[i]的最大值就是整个DAG的最长路径长度。

    int DP(int i)
    {
        if(dp[i] > 0) return dp[i];
        for(int j = 0; j < n; j++)
        {
            if(G[i][j] != INF)
            {
                dp[i] = max(dp[i], DP[j]+G[i][j]);
            }
        }
        return dp[i];
    }

背包问题是一类经典的动态规划问题，下面介绍两类最简单的背包问题：01背包问题和完全背包问题。

有一类动态规划可解的问题，它可以描述成若干个有序的阶段，且每个阶段的状态只和上一个阶段的状态有关，一般把这类问题称为多阶段动态规划问题。

01背包问题：有n 件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都只有1件。

如果采用暴力枚举每一件物品放或者不放进背包，显然每件物品都有两种选择，因此n件物品就有2的n次方种情况，而O(2的n次方)的复杂度显然是很糟糕的。而使用动态规划方法可以将复杂度降为O(nV)。

令dp[i][v]表示前i件物品(1≤i≤n, 0≤v≤V)恰好装入容量为v的背包中所能获得的最大价值。怎么求解dp[i][v]呢？考虑对第i件物品的选择策略，有两种策：

1. 不放第i件物品，那么问题转化为前i- 1件物品恰好装入容量为v的背包中所能获得的最大价值，也即dp[i-1][v]

2. 放第i件物品，那么问题转化为前i- 1件物品恰好装入容量为v-w[i]的背包中所能获得的最大价值，也即dp[i- 1][v-w[i]] + c[i]。

因此状态转移方程为：dp[i][v]=max{dp[i-1][v], dp[i-1][v-w[i]]+c[i]}, (1≤i≤n, w[i]≤v≤V)

由于dp[i][v]表示的是恰好为v的情况，所以需要枚举dp[n][v] (O≤v≤V)，取其最大值才是最后的结果。

    for(int i = 1; i <= n; i++)
    {
        for(int v = w[i]; v <= V; v++)
        {
            dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]] + c[i]);
        }
    }

可以知道，时间复杂度和空间复杂度都是O(nV)，其中时间复杂度已经无法再优化，但是空间复杂度还可以再优化。

可注意到状态转移方程中计算dp[i][v]时总是只需要dp[i - 1][v]左侧部分的数据，且当计算dp[i + 1][] 的部分时，dp[i-1]的数据又完全用不到了（只需要用到dp[i]），因此不妨可以直接开一个一维数组dp[v]（即把第一维省去），枚举方向改变为i从1到n，v从V到0（逆序），这样状态方程可改编为：dp[v] = max(dp[v], dp[v-w[i]]+ c[i]), 1≤i≤n, w[i]≤v≤V

    for(int i = 1; i <= n; i++)
    {
        for(int v = V; v >= w[i]; v--)
        {
            dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
        }
    }

这样01背包问题就可以用一维数组表示来解决了，空间复杂度为0(V)。特别说明：如果是用二维数组存放，v的枚举是顺序还是逆序都无所谓；如果使用一维数组存放，则v的枚举必须是逆序！

完整的求解01背包问题的代码如下：

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int maxn = 100;   // 最大件数
    const int maxv = 1000;  // V的上限

    int w[maxn], c[maxn], dp[maxv];
    int main()
    {
        int n, V;
        scanf_s("%d%d", &n, &V);
        for(int i = 0; i < n; i++)
        {
            scanf_s("%d", &w[i])
        }

        // 边界
        for(int v = 0; v <= V; v++)
        {
            dp[v] = 0;
        }
        for(int i = 1; i <= n; i++)
        {
            for(v = V; v >= w[i]; V--)
            {
                dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
            }
        }

        // 寻找dp中最大的即为答案
        int maX = 0;
        for(int v = 0; v <= V; v++)
        {
            if(dp[v] > maX)
            {
                maX = dp[v];
            }
        }
        printf("%d\n", maX);
    }

完全背包问题的叙述如下：有n种物品，每种物品的单件重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无穷件。

同样令dp[i][v]表示前i件物品恰好放入容量为v的背包中能获得的最大价值。和01背包一样，完全背包问题的每种物品都有两种策略，但是也有不同点。对第i件物品来说：

1. 不放第i件物品，那么dp[i][v] = dp[i-1][v];

2. 放第i件物品，dp[i][v] = dp[i][v-w[i]] + c[i]。

状态转移方程为：dp[i][v]=max{dp[i-1][v], dp[i][v-w[i]]+c[i]}, (1≤i≤n, w[i]≤v≤V)

同样，状态转移方程也可以改写成一维形式，即：dp[i][v]=max{dp[v], dp[v-w[i]]+c[i]}, (1≤i≤n, w[i]≤v≤V)