动态规划（Dynamic Programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

        动态规划的基本步骤：

        1. 描述问题的最优解的结构：确定问题的状态，并定义状态之间的关系。
        2. 递归地定义最优解的值：通常使用自底向上的方式计算最优解的值。
        3. 按自底向上的顺序计算最优解的值：存储中间结果以避免重复计算。
        4. 构造最优解：根据计算得到的最优解的值，构造问题的完整最优解

        背包问题是一类经典的动态规划问题，通常分为01背包和完全背包两种类型。这里以01背包为例进行说明。  

        问题描述：给定一组物品，每种物品都有自己的重量和价值。在限定的总重量内，我们如何选择，才能使得物品的总价值最大。

        状态定义：`dp[i][j]` 表示在前 `i` 个物品中，选择总重量不超过 `j` 的情况下所能得到的最大价值。

        状态转移方程：
        if (weight[i] <= j) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
        } else {
            dp[i][j] = dp[i-1][j];

         代码如下。