递归和循环:跳台阶和变态跳台阶和矩形覆盖

题目描述

跳台阶:一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
变态跳台阶:一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
矩形覆盖:我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

解题思路

看到这样的题，基本上都是一脸蒙蔽，但是其实这样的题，一般都是有规律的，没有规律，那还怎么计算，这个时候学的数学就有用了，找规律。
跳台阶：
1级台阶：1，共1种，
2级台阶：2,11 共2种
3级台阶：12,21,111 共3种
4级台阶：22,211,121,112,1111 共5种
5级台阶：221,212,122,2111,1211,1121,1112,11111共8种
.....看出来规律了fn=f(n-1)+f(n-2)

变态跳台阶：
1级台阶：1，共1种，
2级台阶：2,11 共2种
3级台阶：3,21,12,1111 共4种
4级台阶：4,31,13,22,211,121,112,1111 共8种
5级台阶：5,41,14,32,23,311,131,113,221,212,122,2111,1211,1121,1112,11111共16种
.....看出来规律了fn=2f(n-1)

矩形覆盖：
1的矩阵：1，共1种
2的矩阵4平：2*2,1111，共2种
3的矩阵9平：2*2 + 2*2 + 1, 2*2 + 1*5, 1*9共3种
4的矩阵16平：2*2*4, 2*2*3+1*2, 2*2*1+1*4(2种，2挨着和不挨着), 1*16共5种
.......规律了fn=f(n-1)+f(n-2),可以看出和跳台阶一样

代码实现

        /// <summary>
        /// 循环跳台阶
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int jump(int n) {
            if (n <= 2) {
                return n;
            }

            int first = 1;
            int second = 2;
            int result = 0;
            for (int i = 3; i <= n; i++) {
                result = first + second;
                first = second;
                second = result;
            }

            return result;
        }

        /// <summary>
        /// 变态跳台阶
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int jump(int n) {
            if (n <= 1) {
                return n;
            }

            int first = 1;
            int result = 0;
            for (int i = 2; i <= n; i++) {
                result = 2 * first;
                first = result;
            }

            return result;
        }

想入非非：扩展思维，发挥想象

1. 数学不要忘，学会找规律

2. 不要动不动就用递归