猴子登山：有N个台阶，0<N<=50, 猴子每次只跳1个或者3个台阶，输入N， 输出猴子有多少种方式到达台阶终点

/*
 f1 = 1
 f2 = 1
 f3 = 2
 f4 = f3 + f1 = 3
 f5 = f4 + f2 = 4
 f6 = f5 + f3 = 6
 f7 = f6 + f4 = 9
 */

let input: Int = 50

print("输入：" + String(input))

var fArray: [Int] = [1, 1, 2]

func f(f: Int) -> Int {
    var arr: [Int] = [f]
    var fc = 0;
    while true {
        var arr1: [Int] = [];
        for fi in arr {
            if fArray.count >= fi {
                fc += fArray[fi - 1];
            } else {
                arr1.append(fi - 1)
                arr1.append(fi - 3)
            }
        }
        if arr1.count == 0 {
            break;
        }
        arr = arr1;
    }
    return fc
}

for i in 4 ... input {
    fArray.append(f(f: i))
}

print("输出：" + String(fArray.last!))

输入：50
输出：122106097