算法思想：动态规划 (Dynamic Programming)

什么是动态规划？

动态规划（DP）是一种通过将原问题分解为相互重叠的子问题来解决复杂问题的算法思想。它通常用于优化问题，通过存储子问题的解来避免重复计算。

核心要素

1. 最优子结构: 问题的最优解包含了其子问题的最优解。
2. 重叠子问题: 在求解过程中，许多子问题被反复计算。DP 通过存储这些解来提高效率。
3. 状态转移方程: 定义了问题状态之间如何转换的数学表达式。

经典问题：斐波那契数列

未使用 DP (递归):

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // 大量重复计算
}

使用 DP (自底向上):

#include <vector>

int fib_dp(int n) {
    if (n <= 1) return n;
    std::vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

解题步骤

1. 定义状态: 确定 dp[i] 或 dp[i][j] 代表什么。
2. 找出状态转移方程: 这是最关键的一步。
3. 初始化: 确定 DP 表的初始值。
4. 确定遍历顺序: 保证计算当前状态时，所依赖的状态已经被计算过。

动态规划是一种强大的技术，但需要大量的练习才能熟练掌握。