1.序

近期笔者会写一些博客，与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。

2.动态规划的基本概念[^1]

在学习动态规划之前，先思考这样一个问题：什么是动态规划？为什么叫动态规划？
当读者在试图探索这个问题的时候，不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的，应用于工程领域。
动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

所谓多阶段决策过程是指这样一类决策过程：它可以把一一个复杂问题按时间(或空间)分成若干个阶段，每个阶段都需要作出决策，
以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何，不但与该阶段的经济效果有关，
还影响以后各阶段的经济效果，可见这类多阶段决策问题是一个动态的问题，因此，处理的方法称为动态规划方法。然而，动态
规划也可以处理一些本来与时间没有关系的静态模型，这只要在静态模型中人为地引入“时间”因素，分成时段，就可以把它看作
是多阶段的动态模型，用动态规划方法去处理。

简言之，多阶段决策过程是指这样的一类特殊的活动过程：问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。
下面举例说明什么是多阶段决策问题。
例1（最短路线问题）在线路网络图1中，从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离，为使总运费最少，必须找出一条由A至E总里程最短的路线。

图1
为了找到由A至E的最短线路，可以将该问题分成A—B—C—D—E 4个阶段，在每个阶段都需要作出决策，即在A点需决策下一步到B1还是到B2或B3；同样，若到达第二阶段某个状态，比如B1 ，需决定走向C1还是C2 ；依次类推，可以看出：各个阶段的决策不同，由A至E的路线就不同，当 从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离，而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条路线对应的总路程最短。

3.动态规划算法的基本思想[^2]

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。

图2

但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

图3

4.动态规划的求解步骤[^2]

a. 找出最优解的性质，并刻划其结构特征。
b. 递归地定义最优值。
c. 以自底向上的方式计算出最优值。
d. 根据计算最优值时得到的信息，构造最优解

5.动态规划算法的基本要素[^2]

5.1 最优子结构

• 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
• 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
• 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）

5.2 重叠子问题

• 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
• 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
• 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
  图4

6.一些经典的动态规划问题

题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

分析：
一个问题要使用动态规划求解，一定要满足【最优子结构】，只有满足最优子结构，才能通过子问题的解 构造出 整个问题的解。

在编码时，一般采用【备忘录】或 dp table来实现。
最关键的要找出：该问题的递推关系式（状态转移方程）

假设dp[i][j]=true,表示字符串s从s[i]到s[j]的子串为最长回文子串
反之false.

考虑 abcba 这个示例。如果我们已经知道 bca 是回文，那么要判断 abcba 是不是回文串，只需判断它的左首字母和右尾字母是否相等。这里左=右=a，因此abcba 是回文串

从这里我们可以归纳出状态转移方程
dp[i][j] = true
前提是
dp[i+1][j-1]为true,且 s[i] == s[j]

#include <iostream>
using namespace std;
class MySolution {
public:
    string longestPalindrome(string s) {

        int len = s.size();
        if (len < 2)
            return s;
        //bool dp[len][len];
        bool** dp;
        dp = new bool* [len];
        for (int i = 0; i < len; i++)
            dp[i] = new bool[len];//分配了len行len列的二维数组空间
    
        int max_len=1;//最大回文串长度
        int max_left;//最长回文串的起始位置
        for (int j = 0; j < len; j++)
        {
            for (int i = 0; i < j; i++)
            {
                if (s[j] != s[i])
                    dp[i][j] = false;
                else if (j - i < 3) // (j-1)-(i+1)+1< 2 即表明dp[i][j]是回文串
                    dp[i][j] = true;
                else
                    dp[i][j] = dp[i + 1][j - 1];//s[i]==s[j]
                if (j - i + 1 > max_len && dp[i][j])
                {
                    max_len = j - i + 1;
                    max_left = i;
                }

            }
        }
        return s.substr(max_left, max_len);
        // 用完要释放:
        for (int i = 0; i < len; i++)
        {
            delete[] dp[i]; 
            delete[]dp;
        }   
    }
};
int main()
{
    MySolution sl;
    string s = sl.longestPalindrome("abcdedcabcdefggfedcba");
    cout << s << endl;
}

参考文献
[1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
[2]引用自老师的课件