【数据结构与算法】——动态规划

一、前言

在平时的编程中，你是否遇到过辛辛苦苦写的代码却运行超时的情况？时间复杂度是算法效率的一个重要的指标，该如何优化算法呢？动态规划(简称：DP) 即是一个不错的选择。DP是解决多阶段决策过程中最优化问题的一种常用方法，它在算法中的重要性不言而喻，本文将帮助大家简单了解DP。

二、基本概念

在了解动态规划的基本概念前，我们先说几个动态规划的术语。

2.1 阶段： 将所给问题的过程，恰当的分为若干相互联系的阶段，以便能按一定的次序求解问题。阶段的划分一般是根据时间和空间的特征进行的，但是要能够把问题的过程转化为多阶段决策问题。换句话说就是拆分问题，把一个大规模的问题拆分为多个小规模的问题。

2.2状态： 状态表示每个阶段开始所处的自然状况或者客观条件。其中描述状态的变量称为状态变量。

2.3 决策： 决策表示当过程处于某一阶段某一状态时，可以做出的决定，从而确定下一阶段的状态，这个决定就叫做决策。描述决策的变量称为决策变量，实际问题中决策变量的取值常常限制在某一范围内，此范围称为允许决策集合。

2.4 策略： 由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选择的策略有一定的范围限制，这个范围称为允许策略集合，允许策略集合达到最优效果的策略称为最优策略。

2.5多阶段决策问题: 在解决问题时，决策者在整个决策过程中做出时间上先后有别的多项决策。

明确这几个术语后，我们来给DP下个定义，DP是通过拆分问题（阶段），（通过决策）定义问题状态和状态之间的关系（策略），使得问题能够以多个子问题递推的方式去解决。

三、核心思想

算法的核心思想包括算法的特性和使用条件，动态规划解决的问题需满足无后效性和最优性原理。

3.1无后效性： 某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。这是百度百科给出的定义，有点难以理解。我们来举一个简单的例子，假如小明要从A地前往B地，要求每次只能先前走一步或者先左走一步，当小明走到C地进行决策下一步时，不管小明如何选择都与小明怎么走到C地无关，也就是说“过去不影响未来”。如果改变条件，小明可以任意走但是不能重复走过的路，那么小明在C地时就要考虑不能走之前走过的路了，也就是说“过去影响未来”。

3.2最优性原理： 一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。这个也容易证明，比如前文所说的小明走路问题，如果要找小明从A地到B地最短路径，那么当小明走到C地时，在从C地到B地的路径也必定是最短的，用反证法来说，如果从C地到B地的路径不是最短的，那么从A到B的路径也就不是最短路径了，也就不满足题意了。

3.3状态转移方程： 确定过程由一个状态到另一个状态的演变过程。状态转移方程是动态规划的重点也是难点，找到状态转移方程问题也就迎刃而解了。状态转移方程通常是分析状态之间的递推关系来确定，具体情况因实际问题而有所不同。状态转移方程总是伴随着边界条件，简单理解边界条件就是状态转移方程终止或不满足的条件。

3.4自下而上：从最开始的阶段1通过不断决策迭代进行计算并将结果保存，得到所有阶段解的集合最终解决问题。

结合例题来理解

力扣（LeetCode） 70.爬楼梯 （https://leetcode-cn.com/problems/climbing-stairs）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意： 给定 n 是一个正整数。

示例：

输入：3

输出：3

解释：有三种方法可以爬楼梯。

1. 1阶+1阶+1阶

2. 1阶+2阶

3. 2阶+1阶

我们先来分析下问题，我们把爬n阶楼梯分解为多阶段的子问题，在到达楼顶前每一个阶段我们都有两个决策，爬1个台阶或者爬2个台阶并且易得知满足无后效性，接下来我们找状态转移方程，先来看递推关系，倘若想到达第n阶，那么我们有两种方式，从n-1阶爬1个台阶或者从第n-2阶爬2个台阶，所以递推关系式即是F(n)=F(n-1)+F(n-2)。看到这个关系式，相必大家都不陌生，这不就是斐波那契数列的递推关系式，我用递归把它秒杀了，还需要什么动态规划吗？

需不需要我们来分析下两种算法的效率

首先看递归方法，递归的原理大家都很熟悉，我就不详细介绍了，直接上代码。

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        }
        //递推关系式
        return climbStairs(n - 1) + climbStairs(n - 2); 
    }
}

运行超时

值得一提的是，递归是自上而下的，与我们的动态规划正好相反，我们画个递归树

在进行递归运算时存在大量的重复计算，我们假设数的深度为n，则结点数为2^n 因此时间复杂度为O( n ^ 2)。如果n的值稍微大一些我们的程序就会运行超时。因此我们就像前文中所说的使用动态规划来优化代码。
首先我们先确定DP的状态和转移方程

• 状态变量： dp[n]表示爬n阶台阶的所有可能情况的总和
• 状态转移方程： dp(n) = dp(n-1) +dp(n-2)
• 初始条件： dp(0)=0
• 边界条件： 因为n是正整数，故不需要考虑n<0的情况，等于n即终止状态转移方程

就是我们前文说到的递推关系式，由动态规划特性自下而上，我们每次进行计算后就保存计算结果，这样保证每次计算都只是计算一次，继而解决重复计算的问题。代码如下：

class Solution {
    public int climbStairs(int n) {
        //特判，防止n=1时dp[2]下标越界
         if (n==1) {
            return 1;        
        }
        //定义数组用来存储每次计算的结果
    int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= n; i++) {
            //状态转移方程
            dp[i]=dp[i-1]+dp[i-2]; 
        }
        return dp[n];
    }
}

这样我们就用DP将时间复杂度优化为了O(n),空间复杂度O(n) ,当然我们也可以直接用递推关系式来优化空间复杂度，还可以根据斐波那契数列的闭公式直接解决，因为本文介绍动态规划就不详述了。

解决爬楼梯问题后我们再来看一道题加深印象

力扣（LeetCode） 322.零钱兑换（https://leetcode-cn.com/problems/coin-change）

给定不同面额的硬币 coins 和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

---

示例：

输入：coins = [1,2,5], amount=11

输出：3

解释：11=5+5+1

这道题和爬楼梯和相同之处，决策换成不同硬币的面额，爬到楼顶换成了凑成硬币总金额。假设有n枚硬币凑成总金额amount，那么必定满足第n-1枚硬币的总金额=amount-第n枚硬币的面额，因此我们把凑amount至少所用硬币数转化成了凑amount-第n枚硬币的面额至少所用硬币数。我们可以用一维数组来存储硬币的金额和个数，（当然也可用二维数组）。

• 状态变量：dp[n]表示当前所凑硬币总金额为n，至少所需的硬币数

• 状态转移方程：当n=0时，dp（n）=0.

                   当n<0时，dp（n）=-1.
                   当n>0时，dp（n）={ min（dp（n-coin）+1）| coin∈coins }
  

dp[i] = Math.min(dp[i], dp[i - coin] + 1);

i为硬币的总金额，dp[i] 为最少所用的硬币数

coin为可供选择的硬币面额

• 初始条件： dp（0）= 0 当总金额为0时，所需硬币数为0
• 边界条件： i-coin<0 表示不能凑成所给的总金额amount
  代码如下：

class Solution {
    public int coinChange(int[] coins, int amount) {
     int[] dp = new int[amount + 1];
        //将数组所有数置为最大值 作用：保证可以用给定面额硬币拼凑的总金额数是有意义的
        Arrays.fill(dp, Integer.MAX_VALUE);
        //定义初始条件
        dp[0] = 0;
        //当amount为0时，所需硬币数为0
        if (amount == 0) {
            return 0;
        }
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                //如果可以凑成差值
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    //状态转移方程 可以凑成差值 
                    //在原有的基础上 和 用新面额硬币替换原来的金额并更新硬币个数 两者之中选出最小的硬币个数   
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        //如果dp[amount]=Integer.MAX_VALUE 那么说明用任意所给硬币面额随意拼凑都不能满足amount总金额
        return dp[amount] < Integer.MAX_VALUE ? dp[amount] : -1;
    
    }
}

时间复杂度为O(An) A表示总金额数，n表示硬币面额的个数，我们一共需要计算O（n） 个状态，每个状态需要遍历A次进行状态转移，因此时间复杂度为O（An) , 空间复杂度为O(n)

四、总结

解决动态规划问题的一般步骤

1.划分阶段： 按照具体问题的时间或空间的特征，把问题分成若干个阶段，阶段还需要有顺序，如果没有顺序也就无法进行下一步的决策。
2.确定状态和状态变量： 将每个阶段所处的自然状况或客观条件，用状态变量表示出来，状态要满足无后效性。
3.明确决策找到状态转移方程： 在具体的问题中找到题干中所描述的决策和允许决策集合，由阶段n逆向分析找到推出此阶段的关系式，列出状态转移方程。
4.找到边界条件： 状态转移方程是一个递推式，需要找到终止条件和边界的条件。

最后动态规划作为一种经典算法，它所涵盖的知识是非常广泛和深刻的，本文仅作为动态规划的入门级学习。