递归问题：走台阶

  1/**
  2 * 【递归问题】：如有N个台阶，每次可以走1阶或者2阶，求走完N个台阶的所有方法
  3 *
  4 * <p>
  5 * 如何判断一个问题可以归纳为递归问题？
  6 * <ul>
  7 *     <li>
  8 *         1. 一个问题可以分解为另一个或多个问题的解；
  9 *     </li>
 10 *     <li>
 11 *         2. 原问题与被分解的问题除了数据规模不一样，解决思路一样；
 12 *     </li>
 13 *     <li>
 14 *         3. 存在边界条件，可以终止递归；
 15 *     </li>
 16 * </ul>
 17 * </p>
 18 * <p>
 19 * 结合上述分析，来分析这个台阶问题，若记走完N阶有F(N)种方法。
 20 * <p>
 21 * 已知第一步可以走1阶或者2阶，那么走完剩余的台阶有F(N-1)或F(N-2)种方法，那么有
 22 * <pre>
 23 *     F(N) = F(N-1) + F(N-2) (N>2)
 24 * </pre>
 25 *
 26 * <p>
 27 * 现在看看边界条件，当N=1和N=2时，F(1)=1，F(2)=2。
 28 * <p>
 29 * 因此上述问题的解可记为：
 30 * <pre>
 31 *     /    F(1) = 1
 32 *    |     F(2) = 2
 33 *     \    F(N) = F(N-1) + F(N-2) (N>2)
 34 * </pre>
 35 * <p>
 36 * 以上被称为递推公式，只要有了递推公式，很容易将递归问题用代码实现：
 37 * <pre>
 38 *     int solution(int n){
 39 *         if(n == 1) return 1;
 40 *         if(n == 2) return 2;
 41 *         return solution(n-1) + solution(n-2);
 42 *     }
 43 * </pre>
 44 *
 45 * <p>
 46 * 不过，递归也会存在问题：
 47 * <ul>
 48 *     <li>
 49 *         1. 如果递归深度很大，可能会造成栈溢出(StackOverFlow)；
 50 *     </li>
 51 *     <li>
 52 *         2. 递归过程可能存在重复计算的情形，这样也会造成时间和空间的浪费；
 53 *     </li>
 54 * </ul>
 55 * <p>
 56 * 关于第一个问题，可以在编码时限制递归深度。不过如此处理可能有悖于业务逻辑，
 57 * 需要具体考虑。
 58 * <p>
 59 * 关于重复计算，还以上述问题为例：
 60 * <pre>
 61 *                    F(2)
 62 *                  /
 63 *              F(4)
 64 *            /     \
 65 *          /        F(3) ...
 66 *     F(6)
 67 *          \        F(3) ...
 68 *           \     /
 69 *            F(5)
 70 *                \
 71 *                  F(4) ...
 72 * </pre>
 73 * <p>
 74 * 可以看到，F(4)和F(3)都计算了多次。可以引入一个表，用于记录已经计算过的值，
 75 * 这样可以减少计算的次数。
 76 * <p>
 77 * <b>一般地，所有的递归问题，都可以转化为使用一般代码实现。</b>
 78 *
 79 * @author wangy
 80 * @version 1.0
 81 * @date 2021/7/2 / 10:47
 82 */
 83public class Steps {
 84    private static HashMap<Integer, Integer> resultSet = new HashMap<>();
 85
 86    // 递归实现
 87    // 时间复杂度O(n)，空间复杂度O(n)
 88    static int solution(int n) {
 89        if (n == 1) return 1;
 90        if (n == 2) return 2;
 91        if (resultSet.containsKey(n))
 92            return (int) resultSet.get(n);
 93        int res = solution(n - 1) + solution(n - 2);
 94        resultSet.put(n, res);
 95        return res;
 96    }
 97
 98    // 非递归实现
 99    // 时间复杂度O(n)，空间复杂度O(1)
100    static int solution2(int n) {
101        if (n == 1) return 1;
102        if (n == 2) return 2;
103        int fn_1 = 2;
104        int fn_2 = 1;
105        int res = 0;
106        for (int i = 3; i <= n ; i++){
107            res = fn_1 + fn_2;
108            fn_2 = fn_1;
109            fn_1 = res;
110        }
111        return res;
112    }
113
114    public static void main(String[] args) {
115        int n = 6;
116        System.out.println(solution(n));
117        System.out.println(solution(n) == solution2(n));
118    }
119
120}