LCR 127. 跳跃训练
题目描述：
今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子，每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。
结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
**注意：**与70. 爬楼梯类似
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 5
输出：8
提示
0 <= n <= 100
JAVA代码：
迭代法：
class Solution {
public int trainWays(int num) {
if(num==0) return 1;
if(num==1) return 1;
int[] n = new int[num+1];
n[1] = 1;
n[2] =2;
for(int i =3;i<=num;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(num==0) return 1;
int[] arr = new int[num+1];
return getWay(num,arr);
}
public int getWay(int n,int[] arr){
if(arr[n]>0) return arr[n];
if(n==1){
arr[n] = 1;
}else if(n==2){
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(n<2) 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(n>0){
if((n&1)==1){
res = multiple(res,a);
}
n>>=1;
a = multiple(a,a);
}
return res;
}
public int[][] multiple(int arr1[][],int arr2[][]){
int result[][] = new int[2][2];
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
result[i][j] = (int)(((long)arr1[i][0]*arr2[0][j] + (long)arr1[i][1]*arr2[1][j])%1000000007);
}
}
return result;
}
}
