/**
* 爬梯子
* 斐波那契
* @author Green.Gee
* @date 2022/4/8 14:40
* @email green.gee.lu@gmail.com
*/
public class SolveQ6 {
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.err.println(start);
/**
* 1649408090651
* 20365011074
* 48
*/
// System.err.println(climb(50));
/**
* 1649408500551
* 9079565065540428013
* 0
*/
// System.err.println(climb_bak_1(1000));
/**
* 1649409103840
* 9079565065540428013
* 0
*/
System.err.println(climb_bak_2(1000));
long end = System.currentTimeMillis();
System.err.println((end - start) / 1000);
}
// 递归
public static long climb(int n){
if(n < 1)
return 0;
if(n == 1)
return 1;
if(n == 2)
return 2;
return climb(n - 1) + climb(n - 2);
}
// 动态规划
public static long climb_bak_1(int n){
if(n < 1)
return 0;
if(n == 1)
return 1;
if(n == 2)
return 2;
long[] sum = new long[n];
sum[0] = 1;
sum[1] = 2;
for (int i = 2;i < n;i++){
sum[i] = sum[i - 1] + sum[i - 2];
}
return sum[n - 1];
}
// 迭代-动态规划
public static long climb_bak_2(int n){
if(n < 1)
return 0;
if(n == 1)
return 1;
if(n == 2)
return 2;
long sum0 = 0,sum1 = 1,sum2 = 2;
for (int i = 2;i < n;i++){
sum0 = sum1 + sum2;
sum1 = sum2;
sum2 = sum0;
}
return sum0;
}
}
