1.每次可以走1步，或两步，求走n级台阶的方案个数
分析，其实就是斐波那契数列,无论怎么走,最后一步要么走1级，要么走2级，所以n级方案等于n-1级和n-2级方案之和
import java.util.HashMap; public class WalkStairs { // 上n级台阶 public static int walkStairs(int n) { if (n == 1) return 1; else if (n == 2) return 2; return walkStairs(n - 1) + walkStairs(n - 2); } }
对于上述方案，当n很大时用时会非常长。因为中间存在大量重复的计算结果,例如当n=45时:
walkStairs(45) = walkStairs(44) + walkStairs(43)
walkStairs(44) = walkStairs(43) + walkStairs(42)
walkStairs(43) = walkStairs(42) + walkStairs(41)
对于walkStairs(43),walkStaris(42),...walkStairs(1)都会被计算两遍
2.改进方案:
使用缓存，保存已经计算的结果
public static int walkStairsWithCache(int n) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(1, 1); map.put(2, 2); return _walkStairsWithCache(map, n); } private static int _walkStairsWithCache(HashMap<Integer, Integer> map, int n) { if (map.get(n) != null) return (Integer) map.get(n); int ret = _walkStairsWithCache(map, n - 1) + _walkStairsWithCache(map, n - 2); map.put(n, ret); return ret; }
性能比较:
public static void main(String[] args) { int n = 45; // 楼梯级数 long begin, end; int choices = 0; System.out.println("----------使用缓存------------"); begin = System.currentTimeMillis(); choices = walkStairsWithCache(n); end = System.currentTimeMillis(); System.out.println("使用缓存 走" + n + "级台阶用时:" + (end - begin) + "ms" + "共有" + choices + "中选择"); System.out.println("----------不用缓存------------"); begin = System.currentTimeMillis(); choices = walkStairs(n); end = System.currentTimeMillis(); System.out.println("不用缓存 走" + n + "级台阶用时:" + (end - begin) + "ms" + "共有" + choices + "中选择"); }
效果:
3.规定走n级台阶需要偶数/奇数级步
代码:
// 通过偶数步上n级台阶 public static int walkStairsByEvenSteps(int n) { if (n == 1) return 0; else if (n == 2) return 1; else return walkStairsByOddSteps(n - 1) + walkStairsByOddSteps(n - 2); } // 通过奇数步上n级台阶 public static int walkStairsByOddSteps(int n) { if (n == 1) return 1; else if (n == 2) return 1; else return walkStairsByEvenSteps(n - 1) + walkStairsByEvenSteps(n - 2); }
测试:
public static void main(String[] args) { for (int i = 1; i < 10; ++i) { int steps = walkStairs(i); int oddSteps = walkStairsByOddSteps(i); int evenSteps = walkStairsByEvenSteps(i); System.out.println("走" + i + "级台阶"); System.out.println("共有" + steps + "种方案"); System.out.println("走奇数步有" + oddSteps + "种方案"); System.out.println("走偶数步有" + evenSteps + "种方案"); System.out.println("---------------------"); } }
效果:
走1级台阶 共有1种方案 走奇数步有1种方案 走偶数步有0种方案 --------------------- 走2级台阶 共有2种方案 走奇数步有1种方案 走偶数步有1种方案 --------------------- 走3级台阶 共有3种方案 走奇数步有1种方案 走偶数步有2种方案 --------------------- 走4级台阶 共有5种方案 走奇数步有3种方案 走偶数步有2种方案 --------------------- 走5级台阶 共有8种方案 走奇数步有4种方案 走偶数步有4种方案 --------------------- 走6级台阶 共有13种方案 走奇数步有6种方案 走偶数步有7种方案 --------------------- 走7级台阶 共有21种方案 走奇数步有11种方案 走偶数步有10种方案 --------------------- 走8级台阶 共有34种方案 走奇数步有17种方案 走偶数步有17种方案 --------------------- 走9级台阶 共有55种方案 走奇数步有27种方案 走偶数步有28种方案 ---------------------