【动态规划】斐波那契数列模型

动态规划

动态规划(DP）是一种解决复杂问题的算法思想，将问题分解成更小的子问题，并通过这些子问题来解决问题。

动态规划的基本步骤

确定dp表及dp表中元素的含义；
确定状态转移方程；
初始化dp表；
确定填表顺序；
返回结果

在dp中，基本上都是根据这5步来做的。在动态规划中，有一些经典的题目，例如：斐波那契数列、最长公共子序列、背包问题、最短路径问题等。

本篇主要讲有关斐波那契相关的题目。

1137. 第 N 个泰波那契数 - 力扣（LeetCode）

算法分析

这道题要求第n个泰波那契数，可能你想想到用递归的方法，但这道题用递归来进行会超时。我们用动态规划的方法来解决。看图:

算法代码

/*** 计算泰波那契数列中的第n个数* 泰波那契数列是这样的：0, 1, 1, 2, 4, 7, 13, ...，从第四个数开始，每个数都是前三个数的和* 使用动态规划的方法来解决这个问题，避免了重复计算，提高了效率** @param n 想要计算的泰波那契数列的位置，n >= 0* @return 返回泰波那契数列中第n个数的值*/public int tribonacci(int n) {// 处理初始情况，当n为0时返回0，当n为1或2时返回1if (n <= 2) {return n == 0 ? 0 : 1;}// 创建一个数组，用来保存前n个泰波那契数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];}// 返回第n个泰波那契数的值return dp[n];}

时间复杂度为O(n),空间复杂度为O(n)。

思考：这道题能不能进行优化？

显然是可以，这里我们可以用 滚动数组 的办法来对算法进行优化。

我们可以看到，想要求 dp[i] 那么我们只需要知道dp[i-1]、dp[i-2]、dp[i-3]这三个值，那么我们就可以用三个变量a、b、c来对这三个dp值进行存储,额外借助一个变量d来存储这三个变量值之和。

步骤为：
        d=a+b+c;a=b;b=c;c=d;

算法代码

 /*** 计算n阶特里波那契数列的值* 特里波那契数列是这样一个数列：0, 1, 1, 2, 4, 7, 13, 24, ...* 从第四个数开始，每个数都是前三个数的和* 优化使用迭代方法计算，避免了递归方法的性能问题* * @param n 指定的阶数，n是一个非负整数* @return 返回n阶特里波那契数列的值*/public int tribonacci(int n) {// 处理特里波那契数列的前三个特殊值if(n<=2) return n==0?0:1;// 初始化特里波那契数列的前三个值int a=0,b=1,c=1;// 用于临时存储计算结果的变量int d=0;// 通过迭代计算n阶特里波那契数列的值for(int i=3;i<=n;i++){// 当前项是前三项之和d=a+b+c;// 更新前三个值，为下一次迭代做准备a=b;b=c;c=d;}// 返回n阶特里波那契数列的值return d;}

面试题 08.01. 三步问题 - 力扣（LeetCode）

算法分析

这道题和上面那道题的做法类似。

这里有些细节需要处理：

dp数组需要是long类型，有些数据值超过了int的最大值；

每次dp[i]计算的时候都需要模1000000007。

算法代码

/*** 计算到达第n阶的方法数* 本函数解决的问题是，给定一个整数n，表示楼梯的阶数，求到达第n阶有多少种不同的走法* 规则是每次可以移动1阶、2阶或3阶* * @param n 楼梯的总阶数，n>0* @return 到达第n阶的方法数*/
public int waysToStep(int n) {// 对于前两阶，直接返回阶数本身，因为只有1阶和2阶时，方法数分别是1和2if(n<=2) return n;// 定义模数，用于结果的模运算，以防止计算过程中的整数溢出int MOD = 1000000007;// 创建一个数组用于存储到达每一阶的方法数long[] dp = new long[n + 1];// 初始化已知的到达前三阶的方法数dp[1] = 1;dp[2]= 2;dp[3] = 4;// 从第四阶开始，每一阶的方法数是到达前三阶方法数之和for (int i = 4; i <= n; i++) {dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;}// 返回到达第n阶的方法数return (int) dp[n];
}

时间复杂度为O(n),空间复杂度为O(n)

优化

跟上一道题一样，可以用几个变量来存储值。

/*** 计算到达第n个台阶有多少种走法* 使用动态规划思想，优化空间复杂度* * @param n 第n个台阶* @return 到达第n个台阶的走法数*/public int waysToStep1(int n) {// 如果n小于等于2，直接返回n，因为只有一步和两步时，走法分别是1种和2种if (n <= 2) return n;// 定义模数，用于取模运算，防止结果溢出int MOD = 1000000007;// a、b、c分别代表到达当前台阶前三个台阶的走法数long a = 1;long b = 2;long c = 4;// d用于临时存储当前台阶的走法数long d = 0;// 从第四个台阶开始遍历，计算每个台阶的走法数for (int i = 4; i <= n; i++) {// 当前台阶的走法数是前三个台阶走法数之和d = (a + b + c) % MOD;// 更新a、b、c为下一轮循环做准备a = b;b = c;c = d;}// 返回最后一个台阶的走法数return (int) c;}

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

算法分析

算法代码

/*** 计算最小成本爬楼梯* 给定一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬所需要的体力值* 可以选择从楼梯的第 0 或 1 个台阶开始爬，一旦开始爬，就不能走回头路* 目标是到达楼梯的顶部，楼梯的顶部位于楼梯的末端之后（即数组之外）* 此函数使用动态规划的方法计算到达楼梯顶部所需的最小体力值* * @param cost 从每个台阶向上爬所需的体力值数组* @return 返回到达楼梯顶部所需的最小体力值*/public int minCostClimbingStairs(int[] cost) {// 楼梯的总数int n = cost.length;// dp[i] 表示到达第 i 个台阶所需的最小体力值int[] dp = new int[n+1];// 从第2个台阶开始计算，因为可以从第0或第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];}

时间复杂度O(n),空间复杂度O(n)

解法二

依旧是利用滚动数组的方法，来对空间进行优化。

  /*** 使用动态规划求解最小成本爬楼梯问题** @param cost 每个阶梯的成本数组* @return 返回到达楼梯顶部的最小成本*/public int minCostClimbingStairs(int[] cost) {// 运用动态规划求解// 状态转移方程为：dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i]int n = cost.length;// 动态规划数组，只需要两个变量来存储前两个阶梯的最小成本int[] dp = new int[2];dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < n; i++) {// 计算到达当前阶梯的最小成本int tmp = Math.min(dp[1], dp[0]) + cost[i];// 更新前两个阶梯的最小成本dp[0] = dp[1];dp[1] = tmp;}// 返回最后一个阶梯或倒数第二个阶梯的最小成本中的较小值return Math.min(dp[0], dp[1]);}

解法三

算法代码

 public int minCostClimbingStairs2(int[] cost) {int n = cost.length;int[] dp = new int[n];dp[n- 1]=cost[n-1];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]);}

91. 解码方法

算法分析

这道题相对于前面几道来说，它的状态转移方程要难想一些。

算法代码

/*** 计算一个数字字符串的解码方法数* 解码规则为：数字表示字母，如 "1" 表示 "A"，"2" 表示 "B"，以此类推，直到 "26" 表示 "Z"* * @param ss 待解码的数字字符串* @return 返回解码方法的总数*/
public int numDecodings(String ss) {int n = ss.length();char[] s = ss.toCharArray();int[] dp = new int[n];// 初始化第一个字符的解码方法数，如果第一个字符不是'0'，则有一种解码方法if (s[0] != '0') dp[0] = 1;// 如果字符串只有一个字符，直接返回结果if (n == 1) return dp[0];// 初始化第二个字符的解码方法数，如果前两个字符都不是'0'，则可以各自解码，算一种解码方法if (s[0] != '0' && s[1] != '0') dp[1] += 1;// 将前两个字符组合成一个数字，检查是否在10到26的范围内，如果是，则可以作为一个整体解码，算另一种解码方法int num = (s[0] - '0') * 10 + s[1] - '0';if (num >= 10 && num <= 26) dp[1] += 1;// 从第三个字符开始遍历，更新每个字符对应的解码方法数for (int i = 2; i < n; i++) {// 如果当前字符不是'0'，则当前字符可以单独解码，解码方法数等于前一个字符的解码方法数if (s[i] != '0') {dp[i] += dp[i - 1];}// 将当前字符与前一个字符组合成一个数字，检查是否在10到26的范围内num = (s[i - 1] - '0') * 10 + s[i] - '0';if (num >= 10 && num <= 26) {// 如果在范围内，则当前字符可以与前一个字符组合解码，解码方法数增加前两个字符的解码方法数dp[i] += dp[i - 2];}}// 返回整个字符串的解码方法数return dp[n - 1];
}

细节处理

我们可以看到，其实dp[1]的初始化，跟填表的时候相似，我们可以借助一个小技巧——虚拟节点.

用来处理边界问题以及初始化问题。

算法代码

public int numDecodings1(String ss) {int n = ss.length();char[] s = ss.toCharArray();int[] dp = new int[n+1];dp[0] = 1;if(s[0]!='0') dp[1] = 1;for(int i=2;i<=n;i++){if(s[i-1]!='0'){dp[i] += dp[i-1];}int num = (s[i-2]-'0')*10+s[i-1]-'0';if(num>=10&&num<=26){dp[i] += dp[i-2];}}return dp[n];}