admin 管理员组

文章数量: 1086472

【算法】【递归与动态规划模块】斐波那契数列的系列问题解法及递推类型问题的最优解

目录

  • 前言
  • 问题介绍
  • 解决方案
  • 代码编写
    • java语言版本
    • c语言版本
    • c++语言版本
  • 思考感悟
  • 写在最后

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
有一个楼梯一共num阶，从底层往上层一次只能走1步或者2步，求登上num阶的楼梯一共有几种方式？
如：2阶楼梯，可以一次走2阶也可以走两次1阶，一共有两种方式
进阶问题
有一个农场和一只成熟的母牛，成熟的母牛一年会生一只小母牛，小母牛3年后会成为成熟的母牛并在当年开始产小母牛，问：第num年时，农场一共有多少只母牛？

解决方案

原问题：
方法一：暴力递归
将问题下发到num-1阶和num-2阶即可，num阶的种数=num-1阶的种数+num-2阶的种数
时间：O(2^n)
方法二：动态规划
从第一阶和第二阶开始将到达每一阶的答案都存到数组中，直到计算到num阶为止，arr[num] = arr[num-1] + arr[num-2]
时间：O(n)
方法三：递推动态矩阵法(最优解)
首先将计算num阶和前面的状态关联起来，找到关联关系，也就是：f(num) = f(num-1) + f(num-2)
因此可以建立一个矩阵表达式：
[f(num), f(num-1)] = [f(num-1), f(num-2)] [ 1 1 1 0 ] \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} [11​10​]
通过该表达式可以推出
[f(num), f(num-1)] = [f(2), f(1)] [ 1 1 1 0 ] \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} [11​10​]^（num-2）
因此需要准备一个矩阵相乘和矩阵n次方的公共方法，剩下的工作就比较简单了~详情看代码
时间：O（logn）
进阶问题
方法一：暴力递归
每一年的母牛数等于去年的总牛数加上三年前的总牛数1 , 递归方法很简单
方法二：动态规划
通过递归可以知道动态规划如何解决，非常简单，一维动态规划即可
方法三：递推动态矩阵法(最优解)
首先将计算num阶和前面的状态关联起来，找到关联关系，也就是：f(num) = f(num-1) + f(num-3)
因此可以建立一个矩阵表达式：
[f(num), f(num-1), f(num-2)] = [f(num-1), f(num-2), f(num-3)] [ 1 1 0 0 0 1 1 0 0 ] \begin{bmatrix} 1 & 1 &0 \\ 0 & 0 & 1 \\ 1& 0 & 0 \end{bmatrix} ⎣ ⎡​101​100​010​⎦ ⎤​
通过该表达式可以推出
[f(num), f(num-1)] = [f(2), f(1)] [ 1 1 0 0 0 1 1 0 0 ] \begin{bmatrix} 1 & 1 &0 \\ 0 & 0 & 1 \\ 1& 0 & 0 \end{bmatrix} ⎣ ⎡​101​100​010​⎦ ⎤​^（num-3）

代码编写

java语言版本

矩阵相乘和矩阵n次方代码：

    /*** arr的n次方* @param arr* @param n* @return*/public static int[][] powMartrix(int[][] arr, int n) {if (arr == null || arr.length == 0 || arr[0].length == 0 ) {return arr;}int[][] res = new int[arr.length][arr[0].length];// 单位举证for (int i = 0; i < res.length; i++) {res[i][i] = 1;}for (int i = 0; i < n; i++) {res = multiMartrix(res, arr);}return res;}/*** arr的n次方* 优化版本* @param arr* @param n* @return*/public static int[][] powMartrixPro(int[][] arr, int n) {if (arr == null || arr.length == 0 || arr[0].length == 0 ) {return arr;}int[][] res = new int[arr.length][arr[0].length];// 单位举证for (int i = 0; i < res.length; i++) {res[i][i] = 1;}int[][] tem = arr;for (; n > 0; n >>= 1) {if ((n & 1) != 0){// 这波res需要乘res = multiMartrix(res, tem);}// 准备下一波的乘数，虽然可能不乘tem = multiMartrix(tem, tem);}return res;}/*** 矩阵相乘* @param arr1* @param arr2* @return*/public static int[][] multiMartrix(int[][] arr1, int[][] arr2) {if (arr1 == null || arr1.length == 0 || arr1[0].length == 0|| arr2 == null || arr2.length == 0 || arr2[0].length == 0) {return null;}// 相乘结果：行 = arr1的行 列 = arr2的列数int[][] res = new int[arr1.length][arr2[0].length];// 一行一行来for (int i = 0; i < arr1.length; i++) {for (int j = 0; j < arr2[0].length; j++){int sum = 0;for (int k = 0; k < arr1[0].length; k++) {// 这里的k是arr1的列，arr2 的行sum += arr1[i][k]*arr2[k][j];}res[i][j] = sum;}}return res;}

原问题:

    /*** 阶梯问题：递归解法* O(2^n)* @param num*/public static int process1(int num){if (num == 1) {return 1;}else if (num == 2){return 2;}else if (num == 0){return 0;}else {return process1(num-1) + process1(num - 2);}}/*** 阶梯问题：dp解法* 比递归快非常多* O(n)* @param num*/public static int dp1(int num){int[] dp = new int[num+1];dp[0] = 0;dp[1] = 1;dp[2] = 2;for (int i = 3; i <= num; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[num];}/*** logn解法* 状态矩阵相乘* @param num* @return*/public static int superFunc1(int num) {// 构造一个初始矩阵[func(2), func(1)]int[][] arr = {{2, 1}};arr =  multiMartrix(arr, powMartrixPro(new int[][]{{1,1},{1,0}},num - 2));return arr[0][0];}

进阶问题,（递归和动态规划过于简单，略）：

    /*** 母牛问题* 求第years年时有多少牛* @param years* @return*/public static int cowPro(int years) {if (years <= 3){return years;}int[][] arr = {{3,2,1}};arr = multiMartrix(arr, powMartrixPro(new int[][]{{1,1,0},{0,0,1},{1,0,0}}, years-3));return arr[0][0];}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题是一道典型的递推系列问题，目前感觉基本上很多递归算法都是递推问题，比如典型的二叉树遍历问题，根节点的各种属性依赖于左边和右边子树的属性。
所以以后遇到这种求某个状态时的个数、种数类型问题，可以考虑是否和前面的状态存在依赖关系，如果存在依赖关系就可以使用递推公式解决此类问题。同样，后面的递归和动态规划类型问题都可以使用类似的递推思想解决，这又是一个万能的思路一定要掌握！

对了还有个重要的思想：
矩阵的n次方优化，正常思考任何数或者什么东西的n次方都是累乘法，但是这里有一个非常巨大的优化就是将次方的指数2进制化，比如10的75次方，75可以分解为1001011，也就是64+8+2+1，同时10^75等于10^64 *10 ^8 * 10^2 *10 ^1, 这里可以发现，8是2的三次方，所以10的8次方不需要1次方乘8次，只需要2次方乘3次，同理，64次方可以是8次方的平方，这里的性能提升是非常巨大的，也是logn时间复杂度的精髓！
奇思妙想一下，分解成3进制、10进制为什么不行，非要2进制？
75本身就是10进制，那么75可以分解为70+5， 同时 也就是 10的70次方 * 10的5次方
到这里就可以发现指数之间是没有次方的直接关系的，但是2进制的每一位之间都是存在次方关系的（满2进1的特性，每一位只有两种状态），到这里是可以感受到计算机使用2进制的伟大之处了吧！

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq
再次感谢左大神对我算法的指点迷津！

  1. 这里为什么说是三年前的总牛数呢？因为三年前的总牛数就是三年后的总生产力，三年前的所有牛，三年后都是成熟的，这三年期间新增的牛都不是成熟的，所以三年后，新增的数量=三年前的总牛数！ ↩︎

本文标签： 算法递归与动态规划模块斐波那契数列的系列问题解法及递推类型问题的最优解

版权声明：本文标题：【算法】【递归与动态规划模块】斐波那契数列的系列问题解法及递推类型问题的最优解 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693581255a230489.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。