计算跳到n阶的跳法总数
package com.zxj.algorithm.动态规划;
import lombok.extern.slf4j.Slf4j;
import java.util.Arrays;
/**
* 递归函数 f(n): 计算跳到n阶的跳法总数。
* <p>
* f(0) = 0,
* f(1) = 1,
* f(2) = 2,
* f(n) = f(n-1) + f(n-2)
*/
@Slf4j
public class 爬楼梯 {
/**
* 备忘录
*
* @param data index层的跳法
* @param n 台阶数
* @return 返回第n层的跳法
*/
public static int algorithm(int[] data, int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
}
if (data[n] == -1) {
data[n] = algorithm(data, n - 1) + algorithm(data, n - 2);
}
return data[n];
}
/**
* 动态规划
*
* @param data index层的跳法
* @param n 台阶数
* @return 返回第n层的跳法
*/
public static int algorithm2(int[] data, int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
data[1] = 1;
data[2] = 2;
for (int i = 3; i <= n; i++) {
data[i] = data[i - 1] + data[i - 2];
}
return data[n];
}
}
public static void main(String[] args) {
long startTs;
int n;
int total;
startTs = System.currentTimeMillis();
n = 10;
int[] data = new int[n + 1];
Arrays.fill(data, -1);
total = algorithm(data, n);
log.info("备忘录 number={}, ts={}, total={}", n, System.currentTimeMillis() - startTs, total);
startTs = System.currentTimeMillis();
n = 1000;
data = new int[n + 1];
Arrays.fill(data, -1);
total = algorithm(data, n);
log.info("备忘录 number={}, ts={}, total={}", n, System.currentTimeMillis() - startTs, total);
startTs = System.currentTimeMillis();
n = 10;
data = new int[n + 1];
Arrays.fill(data, -1);
total = algorithm2(data, n);
log.info("动态规划 number={}, ts={}, total={}", n, System.currentTimeMillis() - startTs, total);
startTs = System.currentTimeMillis();
n = 1000;
data = new int[n + 1];
Arrays.fill(data, -1);
total = algorithm2(data, n);
log.info("动态规划 number={}, ts={}, total={}", n, System.currentTimeMillis() - startTs, total);
}
}
运行结果