动态规划算法的欢乐密码(一)：斐波那契数模型

专栏：算法的魔法世界

个人主页：手握风云

目录

一、动态规划

二、例题讲解

2.1. 第 N 个泰波那契数

2.2. 三步问题

2.3. 使用最小花费爬楼梯

2.4. 解码方法

---

一、动态规划

        动态规划是一种将复杂问题分解为更小的子问题，并利用子问题的解来构建原问题的解的方法。它主要用于解决具有重叠子问题和最优子结构特性的问题，通过存储子问题的解（避免重复计算）来提高效率。

        动态规划的解题思路通常可以分为以下几个步骤：（1）定义状态表示；（2）推导状态转移方程；（3）初始化和边界条件；（4）填表顺序；（5）返回值

二、例题讲解

2.1. 第 N 个泰波那契数

        本题可以看作是斐波那契数的加强版，并且首项是从第0项开始计算的。我们先来创建一个一位数组dp[]，这个dp表里面的值就是我们的状态表示。题目要求我们求出第N个泰波那契数，那么dp[i]就表示第i个泰波那契数。dp[i]的表示就是状态转移方程，题目其实给出状态转移方程，dp[i]依赖于前三个状态，dp[i]=dp[i-1]+dp[i-2]+dp[i-3]。接下来就是初始化，保证填表的时候不越界，如果我们使用上面的状态表示方程，dp[0]、dp[1]、dp[2]都会发生越界。而题目也已经将前三个状态给了出来，dp[0]=0、dp[1]=1、dp[2]=1。下面我们填表的时候，为了填写当前状态，所需的状态必须是已经计算出来的，所以填表顺序从左到右。

        完整代码实现：

class Solution {public int tribonacci(int n) {if (n == 0)return 0;if (n == 1 || n == 2)return 1;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;dp[2] = 1;for (int i = 3; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];return dp[n];}
}

        时间复杂度为，因为额外创建了数组，空间复杂度也为。

        空间优化：一般情况下，动态规划都可以利用滚动数组来解决。在这道题中，从第三个数开始，我们仅需前三个数就可以求出当前状态的结果，其他的空间就会产生浪费。使用滚动数组，我们只需要存储最近的三个泰波那契数。如下图，先初始化a、b、c的值，第N个泰波那契数d=a+b+c，当我们要求下一个泰波那契数时，将d的值更新为c，c的值更新为b，b的值更新为a。因为这种求法不用创建数组，空间复杂度可以优化为。

2.2. 三步问题

        当n=1时，只有1种方式。当n=2时，从0直接到2，1种方式；我们不管怎么从0到1，直接考虑从1到2，1种方式，所以0到2一共是1+1=2种方式。当n=3时，从0直接到3，1种方式；从1开始直接到3，1种方式，前面从0到1，1种方式，1*1=1种；从2开始直接到3，1种方式，从0到2，2种方式，2*1=2种方式，所以0到3一共是1+1+2=4种方式；当n=4时，按照上面的推导过程，从0到4一共是1+2+4=7种方式。所以递推公式为：当n>3时，F(n)=F(n-1)+F(n-2)+F(n-3)。

        我们根据题目要求可以得出状态表示为到达n号台阶时，共有多少种方式。这个小孩一次可以上1阶、2阶、3阶台阶，我们以第n阶台阶最近的一步划分，那么状态转移方程为：dp[n]=dp[n-1]+dp[n-2]+dp[n-3]。当n<4时，这个状态转移方程就没有意义了，初始化操作，dp[1]=1，dp[2]=2，dp[3]=4。根据题目要求，填表顺序为从左到右。

        完整代码实现：

class Solution {public int waysToStep(int n) {// 定义模数，用于防止结果溢出int mod = (int) 1e9 + 7;if (n == 1 || n == 2) return n;if (n == 4) return 4;int[] dp = new int[n + 1];// 初始化前三个台阶的方法数dp[1] = 1;dp[2] = 2;dp[3] = 4;// 从第4个台阶开始，计算每个台阶的方法数for (int i = 4; i <= n; i++) {// 到达第i个台阶的方法数为前三个台阶的方法数之和，并取模防止溢出dp[i] = ((dp[i - 1] + dp[i - 2]) % mod + dp[i - 3]) % mod;}return dp[n];}
}

2.3. 使用最小花费爬楼梯

        题目给出了一个长度为n的数组cost，其中cost[i]表示爬到第i个台阶所需要的花费。目标是计算出从底部爬到顶部所需的最小花费。我们首先要明白楼梯顶部在哪里，这里不是数组的最后一个元素，而是越过数组末尾的下一个位置。

• 第一种解法

        根据题目分析可以得出，本题的状态表示为到达n阶台阶时，最小花费的数目。接着利用之前的状态来推导dp[n]的值，根据最近的一步或者两步来划分问题：先到达dp[n]的前一个位置dp[n-1]，然后支付cost[n-1]走一步，到达dp[n]花费为dp[n-1]+cost[n-1]；先到达dp[n-2]的前两个位置dp[n-2]，然后支付cost[n-2]走两步，花费为dp[n-2]+cost[n-2]。那么递推公式dp[n]=Math.min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2])。初始化dp[0]=dp[1]=0。填表顺序从左到右。

        完整代码实现：

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n + 1];for (int i = 2; i <= n; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];}
}

• 第二种解法 

        第一种解法是利用结尾作为状态表示，第二种我们以起点作为状态表示。这里dp[i]表示从i位置出发到达楼顶的最小花费。状态转移方程：当我们支付cost[i]向后走一步到达i+1位置时，再从i+1位置到达终点，花费为dp[i+1]+cost[n]；当我们支付cost[i]向后走两步到达i+2位置时，再从i+2位置到达终点，花费为dp[i+2]+cost[n]，所以递推公式为dp[i]=Math.min(dp[i+1],dp[i+2])+cost[i]。接着将dp表最后两个元素初始化，仅需支付这一层台阶的花费到达终点即可，所以dp[n-1]=cost[n-1]，dp[n-2]=cost[n-2]。填表顺序从左到右。起始位置要从0下标或者1下标开始爬楼梯，最后要返回dp[0]与dp[1]的最小值。

        完整代码实现：

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n];// 初始化dp数组的最后一个元素，即到达最后一阶楼梯的花费dp[n - 1] = cost[n - 1];// 初始化dp数组的倒数第二个元素，即到达倒数第二阶楼梯的花费dp[n - 2] = cost[n - 2];for (int i = n - 3; i >= 0; i--) {// 到达当前阶楼梯的最小花费等于到达下一阶或下两阶楼梯的最小花费加上当前阶的花费dp[i] = Math.min(dp[i + 1],dp[i + 2]) + cost[i];}return Math.min(dp[0],dp[1]);}
}

2.4. 解码方法

        题目给定一个只包含数字的非空字符串，要求计算解码方法的总数。如果没有合法的方式解码整个字符串，返回0。

        状态表示：以i位置为结尾，从0到i计算字符串有多种解码方式，题目当中要求计算总字符串的解码方式，所以dp[i]表示以i位置为结尾，解码方法的总数。状态转移方程：根据最近的一步，让i位置单独解码，或者以i-1和i结合进行解码（我们在算i+1位置时，会考虑i与i+1结合，所以在计算i位置时，不必考虑i与i+1结合）。当i位置单独解码时，1<=i<=9时成功解码，反之失败。如果0到i-1之间的解码数dp[i-1]，再加上i位置解码，也是dp[i-1]种，如果失败，则整体解码也失败。当i-1与i位置结合时，10<=10*(i-1)+i<=99才能解码成功，整体解码数为dp[i-2]，失败则没有。dp[i]=dp[i-1]+dp[i-2]。初始化：如果0位置解码成功，dp[0]=1，反之dp[1]=1；dp[1]结合上面的推导，可以出现0、1、2三种情况。填表顺序从左到右。结果直接返回dp[i]。

        完整代码实现：

class Solution {public int numDecodings(String s) {int n = s.length();char[] ch = s.toCharArray();int[] dp = new int[n]; // 创建一个动态规划数组，用于存储每个位置的解码方式数量//初始化第一个位置if (ch[0] != '0') dp[0] = 1;if (n == 1) return dp[0];//初始化第二个位置if (ch[1] != '0' && ch[0] != '0') dp[1] += 1;int t = (ch[0] - '0') * 10 + ch[1] - '0';if (t >= 10 && t <= 26) dp[1] += 1;for (int i = 2; i < n; i++) {//单独解码if (ch[i] != '0') dp[i] += dp[i - 1];//结合解码int tt = (ch[i - 1] - '0') * 10 + ch[i] - '0';if (tt >= 10 && tt <= 26) dp[i] += dp[i - 2];}return dp[n - 1]; // 返回最后一个位置的解码方式数量，即为字符串的总解码方式数量}
}

• 边界处理和初始化的优化

        前面三道题的初始化代码非常简单，但这道题的初始化却有很多，并且还存在相似的代码。而接下来就是创建虚拟头结点来对初始化的代码进行优化。我们先将旧的dp表新增一个结点，并将旧dp表里的元素统一后移一位。这里需要注意，1.虚拟结点的值要保证后面填表的正确性，2.下标的映射关系。dp[2]的状态取决于dp[0]和dp[1]，根据前面的状态转移方程，需要+dp[0]时，说明0和1位置可以解码成功，所以dp[0]初始化为1，解码不成功直接忽略。当我们在新dp表里面初始化dp[0]时，我需要看字符串0位置的解码情况。所以只需在新dp表里面-1就可以。

        优化后的代码：

class Solution {public int numDecodings(String s) {int n = s.length();char[] ch = s.toCharArray();int[] dp = new int[n + 1]; // 创建一个动态规划数组，用于存储每个位置的解码方式数量//初始化第一个位置dp[0] = 1;//初始化第二个位置if(ch[1 - 1] != '0') dp[1] = 1;for (int i = 2; i <= n; i++) {//单独解码if (ch[i - 1] != '0')dp[i] += dp[i - 1];//结合解码int tt = (ch[i - 2] - '0') * 10 + ch[i - 1] - '0';if (tt >= 10 && tt <= 26)dp[i] += dp[i - 2];}return dp[n]; // 返回最后一个位置的解码方式数量，即为字符串的总解码方式数量}
}