扬州市建设局网站,服装网站建设目标客户,如何做网站咨询,绵阳建网站LCR 127. 跳跃训练 题目描述#xff1a;
今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子#xff0c;每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中#xff0c;学员们共有多少种不同的跳跃方式。
结果可能过大#xff0c;因此结果…LCR 127. 跳跃训练 题目描述
今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中学员们共有多少种不同的跳跃方式。
结果可能过大因此结果需要取模 1e971000000007如计算初始结果为1000000008请返回 1。
**注意**与70. 爬楼梯类似
示例 1
输入n 2
输出2示例 2
输入n 5
输出8提示 0 n 100 JAVA代码 迭代法
class Solution {public int trainWays(int num) {if(num0) return 1;if(num1) return 1;int[] n new int[num1];n[1] 1;n[2] 2;for(int i 3;inum;i){n[i] (n[i-1]n[i-2]) %1000000007;}return n[num];}
}递归方法
class Solution {static final int MOD 1000000007;public int trainWays(int num) {if(num0) return 1;int[] arr new int[num1];return getWay(num,arr);}public int getWay(int n,int[] arr){if(arr[n]0) return arr[n];if(n1){arr[n] 1;}else if(n2){arr[n] 2;}else{arr[n] (getWay(n-1,arr) getWay(n-2,arr)) % MOD;}return arr[n];}
}矩阵快速幂
看不懂…可以了解一下。
//费波切纳数列
class Solution {public int numWays(int n) {if(n2) return 1;int a[][] {{1,1},{1,0}};int result[][] pow(a,n);return result[0][0];}public int[][] pow(int a[][],int n){int res[][] {{1,0},{0,1}};while(n0){if((n1)1){res multiple(res,a);}n1;a multiple(a,a);}return res;}public int[][] multiple(int arr1[][],int arr2[][]){int result[][] new int[2][2];for(int i 0;i2;i){for(int j 0;j2;j){result[i][j] (int)(((long)arr1[i][0]*arr2[0][j] (long)arr1[i][1]*arr2[1][j])%1000000007);}}return result;}
}
