动态规划问题

动态规划（dynamic programming） 是一种通过将复杂问题分解为更小的子问题来解决的技术。

解题思路

1. 确定状态
2. 建立状态转移方程
3. 确定边界条件
4. 确定递推顺序

经典问题

青蛙跳台阶问题

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

解题思路

1. 确定状态：跳上第n级台阶的方法数
2. 建立状态转移方程：f(n) = f(n-1) + f(n-2)
3. 确定边界条件：f(0) = 1, f(1) = 1
4. 确定递推顺序：从前往后
5. 设计状态空间：f(n)

代码实现

function jump(n: number): number {
    if (n === 0 || n === 1) return 1;
    let a = 1, b = 1;
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}