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

目录

​动态规划

动态规划的基本步骤

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

 算法分析

算法代码

算法代码

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

算法分析

 算法代码

优化

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

算法分析

 ​编辑

算法代码

解法二

解法三

算法代码

 91. 解码方法

算法分析

算法代码

细节处理

算法代码

---

动态规划

动态规划(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时返回1 if (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和2 if(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]; }

---

以上就是本篇所有内容~

若有不足，欢迎指正~