一、什么是动态规划？
动态规划（Dynamic Programming，简称 dp）是一种通过将复杂问题分解为更小的子问题来解决的算法思想，尤其适用于具有重叠子问题和最优子结构的优化问题。其核心目标是避免重复计算，通过存储中间结果（记忆化）来提升效率。
动态规划 vs 分治法
- 共同点：都将问题分解为子问题。
- 区别：
- 分治法（如归并排序）的子问题独立，无重叠，无需存储中间结果。
- 动态规划的子问题有重叠，需存储中间结果避免重复计算。
二、动态规划的使用步骤
为了方便理解下面我将从感性的角度来给大家讲解动态规划的使用步骤。
1. 状态表示
首先在解决问题的时候我们通常会使用一块空间来记录已处理的数据，我们把这块空间叫作 dp 表。
当我们在解决一个小问题时需要借助之前已解决的问题的数据，就可以到 dp 表里面查，当前这个小问题解决后继续把它相关的信息存到 dp 表，然后继续解决下一个小问题。
这个 dp 表中的一小块数据表示什么？这些问题指的就是状态表示。在用动态规划解决问题时，要面对最重要的问题就是 dp 表的状态应该表示是什么？
在解决这个问题时我们通常都是从这几个角度去思考：
- 经验 + 题目要求
- 分析问题的过程中，发现重复子问题。
- 当我们发现子问题后，假设前（或后）几个小问题已经解决，思考我们在解决当前问题时有没有需要前面已解决的问题的什么信息？
2. 状态转移方程
dp[i] 等于什么？这就是状态转移方程。它通常要依赖于已经计算过的状态。
3. 初始化
在创建好 dp 表后主要任务就是对 dp 表的填写，初始化 dp 表的作用有以下两点：
- 保证填表的时候不越界。
- 保证填表的正确性。
4. 填表顺序
为使填写当前状态的时候，所需要的状态已经计算过了。
5. 返回值
最后结合题目要求和状态表示计算结果并返回。
三、试题讲解
1. 最小花费爬楼梯
首先我们分析题目，我们的起点是 0 或 1 的位置，而终点是 n 位置（注意不是 n-1 位置）。我们在爬楼梯时支付一次费用可以爬一个或两个台阶。
当我们尝试从动态规划方向去解决，那么我们试着去构造一下相同的子问题，并且假设它已经解决。
注：为了方便在下文我都会把动态规划简称为'动规'
用动规解题过程中，在找子问题时我总结了一个很厉害的小技巧，就是保留主问题的逻辑，而换一个问题的对象。比如这里，主问题是从起点爬到楼顶的最小花费，那么构造子问题时我们只需要保留这个问题的逻辑，而把楼顶这个对象改成任意位置 i。那么我们就得到了一个子问题（即从起点爬到 i 位置的最小花费）。然后我们再假设前面的相同的子问题已经解决。
动规题复杂多变，以上技巧可以解决大部分的基础动规题，但更多的只是作为一个小经验，并不是所有动规题都可以通过构建子问题来解决的。
在解一个题时，状态表示可以是很多，不同的状态表示就决定了不同的状态转移方程，而要判断一个状态表示是否正确只需看是否能根据该状态表示推出正确的状态转移方程。
能够理解上图那么动态规划的五步骤就水到渠成了。
状态表示：dp[i]：表示爬到 i 时的最小花费 状态转移方程：dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]) 初始化：dp 表初始化为全 0 填表顺序：从下标为 2 的位置开始，并且从左往右填写 返回值：return dp[n]
代码示例：
class {
:
{
n=cost.();
;
( i=;i<=n;i++)
dp[i]=(dp[i]+cost[i],dp[i]+cost[i]);
dp[n];
}
};
