问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

解题思路

这是一个典型的动态规划问题。我们可以使用递归的方式来解决这个问题。

假设青蛙跳上n级台阶的跳法总数为f(n)，那么青蛙跳上n级台阶的跳法可以分解为以下两种情况：

1. 青蛙从n-1级台阶跳上n级台阶，此时跳法总数为f(n-1)；
2. 青蛙从n-2级台阶跳上n级台阶，此时跳法总数为f(n-2)。 因此，青蛙跳上n级台阶的跳法总数f(n)可以表示为：

f(n) = f(n-1) + f(n-2)

// 根据以上公式可以写出以下函数，通过递归方式计算值。
function jump(n: number): number {
    if (n <= 2) {
        return n;
    }
    return jump(n - 1) + jump(n - 2);
}

但是，递归的方式可能会导致重复计算，因此我们可以使用动态规划的方式来解决这个问题。

代码实现

// 其核心点就是最新一节跳法数等于前两节跳法数之和
function jump(n: number): number {
    if (n <= 2) {
        return n;
    }
    let old_num = 1;
    let new_num =2;
    for (let i = 2; i < n; i++) {
        // 临时值存储上一阶跳法
        const temp = new_num;
        // 最新台阶跳法
        new_num = new_num + old_num
        // 更新旧台阶跳法
        old_num = temp
    }
    return new_num;
}

测试

console.log(jump(10)); // 输出：89

总结

青蛙跳台阶问题是一个经典的动态规划问题，我们可以使用递归和动态规划的方式来解决这个问题。

递归的方式比较简单，但是可能会导致重复计算，因此我们使用动态规划的方式来解决这个问题。

动态规划的方式可以避免重复计算，提高算法的效率。