请写出动态规划的思路

动态规划是一种通过将复杂问题分解成更小的子问题并存储解决方案，以便在未来遇到相同的子问题时可以直接重用这些解决方案来解决问题的算法设计技巧。它的核心思想可以总结为以下几步：

1. **明确问题的最小子问题**：确定问题中最小可行的、独立的部分，这是递归的基础。

2. **定义状态转移方程**：对于每一个子问题，定义一个表示其价值的状态，并给出如何通过子问题的解来计算当前问题的解的公式。

3. **创建一个表格或数组**：初始化一个二维数组或一维数组，用于存储所有子问题的解，按照子问题的规模从小到大排列。

4. **填充表格**：自底向上（或者说由小到大），通过已知的子问题结果逐步计算出更大规模问题的结果。这一步是动态规划的关键，避免了重复计算。

5. **获取最终解**：当填充完整个表格后，问题的全局最优解往往对应于最大的（或最小的，取决于问题的具体情况）状态值。

6. **剪枝（可选）**：对于某些特殊结构的问题，可能存在不必要的计算，可以通过一些启发式方法提前终止递归过程。

动态规划常用于优化问题，如最长公共子序列、背包问题等。