动态规划（Dynamic Programming, DP）是一种在解决复杂问题时通过拆解为更小的子问题来求解的技术。动态规划可以帮助我们优化算法的效率，特别是在处理涉及递归、组合问题等复杂计算时。

动态规划概述

动态规划是一种自底向上的解题方法，它通过记录和重复利用子问题的解来避免重复计算，从而极大地提高了效率。动态规划的核心思想在于识别问题的最优子结构（Optimal Substructure）和子问题重叠性（Overlapping Subproblems）。简单来说，当一个问题可以通过解决它的多个子问题来构建出最终解时，动态规划就是一个合适的工具。

动态规划的关键步骤：

1. 定义状态：找出问题的解可以分解为哪些子问题。
2. 转移方程：找到从一个状态转移到另一个状态的递推关系。
3. 初始条件：定义基本的初始解。
4. 最终解：利用这些子问题的解构建出原问题的解。

斐波那契数列的动态规划解法

斐波那契数列是动态规划中常见的经典问题。斐波那契数列的定义是： [ F(n) = F(n-1) + F(n-2) ] 其中，初始条件为： [ F(0) = 0, \quad F(1) = 1 ]

递归解法（效率较低）

初学者在面对斐波那契问题时，通常会首先想到递归实现。然而，递归方法会带来大量的重复计算，从而导致效率低下，时间复杂度为 O(2^n)。代码如下：

function fib(n: number): number {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

对于较大的 n 值，递归计算的时间将成指数增长。这时，我们可以通过动态规划来优化这个问题。

动态规划解法（高效）

动态规划的思想是将每一个子问题的结果存储起来，避免重复计算。通过这种方式，可以将时间复杂度降至 O(n)，代码如下：

function fib(n: number): number {
    if (n <= 1) return n;
    const dp: number[] = new Array(n + 1).fill(0);
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

这里，dp 数组用于保存每个 F(i) 的值，从而避免了重复计算。通过遍历一次数组，便可以得到所需的结果。这就是动态规划最简单的应用。

背包问题的动态规划解法

背包问题是另一个经典的动态规划问题，通常分为0-1 背包问题和完全背包问题。本文主要讲解 0-1 背包问题。

问题描述

0-1 背包问题可以表述为：给定若干物品，每个物品有其重量和价值，背包有固定的承重能力。我们需要在不超过背包承重能力的前提下，选择物品使得其总价值最大。每个物品只能选一次，因此称为 0-1 背包问题。

设有 n 个物品，每个物品的重量为 w[i]，价值为 v[i]，背包的最大承重能力为 W，求背包能装下的最大价值。

递归解法

递归解法往往通过枚举每一个物品是否放入背包来求解。该解法的时间复杂度为 O(2^n)，因为每个物品有两种选择：放入或不放入背包。递归解法的代码如下：

function knapsack(W: number, weights: number[], values: number[], n: number): number {
    if (n === 0 || W === 0) return 0;

    if (weights[n - 1] > W) {
        return knapsack(W, weights, values, n - 1);
    } else {
        return Math.max(
            knapsack(W, weights, values, n - 1), // 不选择第n个物品
            values[n - 1] + knapsack(W - weights[n - 1], weights, values, n - 1) // 选择第n个物品
        );
    }
}

动态规划解法

与斐波那契数列类似，0-1 背包问题也存在大量重复计算，使用动态规划可以将其时间复杂度降低到 O(nW)，其中 n 是物品数量，W 是背包容量。

我们定义一个二维数组 dp[i][j]，表示在前 i 个物品中选择重量不超过 j 的最大价值。状态转移方程为：

[ dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]) ]

即我们可以选择不放第 i 个物品，或者选择放入第 i 个物品，取两者的最大值。初始条件为：dp[0][j] = 0 表示没有物品时总价值为 0。

动态规划代码如下：

function knapsack(W: number, weights: number[], values: number[], n: number): number {
    const dp = Array(n + 1).fill(null).map(() => Array(W + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= W; w++) {
            if (weights[i - 1] > w) {
                dp[i][w] = dp[i - 1][w];
            } else {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[n][W];
}

动态规划中的优化技巧

1. 空间优化

在解决动态规划问题时，往往我们只需要关注当前状态和前一个状态的结果，因此可以通过滚动数组来优化空间复杂度。例如，在背包问题中，我们可以将二维数组压缩为一维数组来减少空间使用。

2. 记忆化递归

记忆化递归是通过将递归中的结果保存到一个缓存中，从而避免重复计算，达到与动态规划相同的效果。它结合了递归的简单性和动态规划的高效性。

function memoFib(n: number, memo: Map<number, number> = new Map()): number {
    if (memo.has(n)) return memo.get(n)!;
    if (n <= 1) return n;

    const result = memoFib(n - 1, memo) + memoFib(n - 2, memo);
    memo.set(n, result);

    return result;
}