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]引用自老师的课件

1动态规划思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。
动态规划的过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

2适用场景

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

• 最优化原理：假设问题的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
• 无后效性：即某阶段状态一旦确定。就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响曾经的状态。仅仅与当前状态有关。
• 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到（该性质并非动态规划适用的必要条件，可是假设没有这条性质。动态规划算法同其它算法相比就不具备优势）。

3动态规划的三大基本要素

动态规划简单来说就是，利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三大基本要素：

• 确定状态和保存状态变量
  将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。最简单的就是用数组来保存当前的每一个状态，这个状态就是每个子问题的决策。
• 确定决策并写出状态转移方程
  因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
• 确定边界条件
  确定边界条件其实就是跟递归的终止条件是类似的。给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

4解题步骤

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
根据动态规划的三大基本要素可以设计解题步骤如下：

• 状态定义： 每个状态的决策，存放每个状态的变量，
• 状态转移方程： 当前状态与上一个状态之间的关系
• 初始状态： 初始的状态或者边界条件

5例题分析

5.1斐波拉契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……
斐波那契数列以如下被以递推的方法定义：
$$F(1)=1，F(2)=1,F(n)=F(n-1)+F(n-2)（n\ge 3，n\in N^{\ast }）$$

5.1.1递归法求解

由上篇文章递归算法递归算法详解——递归算法的三要素以及例题分析
.
可以写出递归形式的求解为

class Solution {
    private final int model = 1000000007;
    public int fib(int n) {
        if (n < 2){
            return n;
        }
        return ((fib(n - 1) % model + fib(n - 2) % model )) % model;
    }
}

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。防止溢出。

若用递归法提交答案后可以看出会超出时间限制。

分析可以看出，在递归时会重复计算，如下所示，以F(6)为例：

复杂度分析

• 时间复杂度分析： $O(n)$.。最大递归次数是$n$。
• 空间复杂度分析： $O(1)$。使用常数大小的额外空间。

5.1.2动态规划求解

• 状态定义： 设 $dp$ 为一维数组，其中 $dp[i]$ 的值代表 斐波那契数列第 $i$ 个数字 。
• 转移方程： $dp[i+1]=dp[i]+dp[i-1]$，即对应数列定义 $f(n+1)=f(n)+f(n-1)$ ；
• 初始状态： $dp[0]=0,dp[1]=1$ ，即初始化前两个数字； 返回值： $dp[n]$ ，即斐波那契数列的第 $n$ 个数字。

空间复杂度优化
若新建长度为 $n$ 的 $dp$ 列表，则空间复杂度为 $O(N)$ 。

由于 $dp$ 列表第 $i$ 项只与第 $i-1$ 和第 $i-2$ 项有关，因此只需要初始化三个整形变量 $sum,a,b$ ，利用辅助变量 $sum$ 使 $a,b$ 两数字交替前进即可 （具体实现见代码） 。
节省了 $dp$ 列表空间，因此空间复杂度降至 $O(1)$ 。

class Solution {
    public int fib(int n) {
        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

复杂度分析

• 时间复杂度分析： $O(n)$.。最大循环次数是$n$
• 空间复杂度分析： $O(1)$。使用常数大小的额外空间。

5.2剑指offer 42 连续子数组的最大和

题目描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为$O(n)$。
示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

动态规划解析：

• 状态定义： 设动态规划列表 $dp$ ，$dp[i]$ 代表以元素 $nums[i]$为结尾的连续子数组最大和。
  \qquad 为何定义最大和 $dp[i]$ 中必须包含元素 $nums[i]$ ：保证 $dp[i]$ 递推到 $dp[i+1]$ 的正确性；如果不包含$nums[i]$ ，递推时则不满足题目的 连续子数组 要求。

• 转移方程： 若 $dp[i-1]\le 0$，说明 $dp[i-1]$ 对 $dp[i]$ 产生负贡献，即 $dp[i-1]+nums[i]$ 还不如 $nums[i]$ 本身大。
  \qquad 当 $dp[i-1]>0$ 时：执行$ dp[i] = dp[i-1] + nums[i]$ ；
  \qquad 当 $dp[i-1]\le 0$ 时：执行 $dp[i]=nums[i]$；

• 初始状态： $dp[0]=nums[0]$，即以$nums[0]$ 结尾的连续子数组最大和为 $nums[0]$ 。

• 返回值： 返回 $dp$ 列表中的最大值，代表全局最大值。

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度 $O(N)$ ： 线性遍历数组 $nums$ 即可获得结果，使用 $O(N)$ 时间。
• 空间复杂度 $O(1)$ ： 使用常数大小的额外空间。

3.1示例1：42.接雨水

题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
输入输出描述
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
图解模型

直观思想

在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此，可以通过动态编程解决。
算法流程

• 找到数组从下标$i$到最左端最高的条形块高度left_max
• 找到数组从下表$i$到最右端最高的条形块高度right_max
• 扫描数组height并更新答案：
  \quad 累加min(max_left[i], max_right[i]) - height[i]到ans上

代码实现

    public int trap(int[] height) {
        int len = height.length;
        if (len < 2) return 0;
        int ans = 0;
        int[] max_left = new int[len];
        int[] max_right = new int[len];
        max_left[0] = height[0];
        for (int i = 1; i < len; i++) {
            max_left[i] = Math.max(height[i], max_left[i - 1]);
        }
        max_right[len - 1] = height[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            max_right[i] = Math.max(height[i], max_right[i + 1]);
        }
        for (int i = 1; i < len - 1; i++) {
            ans += Math.min(max_right[i], max_left[i]) - height[i];
        }
        return ans;
    }

复杂度分析：

• 时间复杂度：$O(n)$。储存最大高度数组需要两次遍历，计算出ans结果遍历一次。
• 空间复杂度：$O(n)$。使用2个n数组存放left_max和right_max数组。

两大性质

1.最优子结构
2.子问题重叠性质

最优子结构

定义
问题的最优解包含着其子问题的最优解。这种性质称为最优子结 构性质。
证明
首先假设由问题的最优解导出的子问题的解不是最优的。
然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从 而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式从子问题的最优 解逐步构造出整个问题的最优解。 最优子结构是问题能用动态规划算法求解的前提

重叠子问题

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
特点：动态规划算法正是利用了这种重叠子问题的性质，对每个子问题只解一次，而后将其保存在一个表格中再次需要时直接调用

时间复杂性：通常不同的子问题个数随问题的大小呈多项式增长 因此用动态规划算法只需要多项式时间，从而获得较高的解题效率

备忘录方法

备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方 法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解

备忘录方法VS动态规划
备忘录方法：计算次序自顶向下，且当部分子问题可不必求解时好

动态规划：计算次序自底向上 ，当一个问题的所有子问题都至少要解一次时好