什么是动态规划？
动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为更简单的子问题来求解的方法。它通常用于优化问题，即寻找最优解的问题。动态规划的核心思想是记住已经解决过的子问题的答案，从而避免重复计算。
动态规划有两种主要的实现方式：自顶向下的记忆化搜索和自底向上的迭代方法。记忆化搜索利用递归，在计算过程中记录子问题的结果；而迭代方法则从最基本的问题开始，逐步构建出最终问题的解。
动态规划的应用场景
动态规划适用于具有重叠子问题和最优子结构的问题。重叠子问题是说同一个子问题会被多次求解，而最优子结构则是指问题的最优解可以通过其子问题的最优解得到。
一些常见的应用场景包括：
- 路径问题：如最短路径、最长路径。
- 背包问题：如何选择物品放入背包，使得背包中的物品价值最大。
- 序列问题：如最长递增子序列、最长公共子序列。
- 字符串问题：如编辑距离、字符串匹配等。
动态规划的基本步骤
解决动态规划问题一般遵循以下步骤：
1. 定义状态
首先明确每个子问题的状态，通常用一个或多个变量表示。状态的选择直接影响到问题的复杂度和解决方案的效率。
2. 状态转移方程
定义状态之间的关系，即如何通过较小规模的子问题求解较大规模的子问题。这是动态规划的核心部分，需要仔细分析子问题间的联系。
3. 边界条件
确定基本状态的值，这些是最小规模子问题的解。边界条件是递归的出口，也是迭代的起点。
4. 计算顺序
根据状态转移方程确定计算顺序。对于记忆化搜索，是从大到小递归求解；对于迭代方法，则是从最小规模子问题开始，逐步求解更大规模的问题。
5. 结果
根据状态定义和状态转移方程，得到最终问题的解。
实例解析：最长递增子序列
最长递增子序列（Longest Increasing Subsequence, LIS）是指在一个给定的序列中找到最长的严格递增子序列。我们使用动态规划来解决这个问题。
1. 定义状态
设dp[i]表示以第i个元素结尾的最长递增子序列的长度。
2. 状态转移方程
对于每个i，我们需要检查所有j < i的情况，如果nums[j] < nums[i]，那么dp[i] = max(dp[i], dp[j] + 1)。这表示我们可以将nums[i]添加到以nums[j]结尾的递增子序列后面。
3. 边界条件
对于所有的i，初始时dp[i] = 1，因为每个元素自身都可以构成一个长度为1的递增子序列。
4. 计算顺序
我们从左到右遍历数组，依次计算每个dp[i]的值。
5. 结果
最终答案是dp数组中的最大值。
-- -------------------- ---- -------
-------- ----------------- -
-- ------------ --- -- ------ --
--- -- - --- ---------------------------
--- ---- - - -- - - ------------ ---- -
--- ---- - - -- - - -- ---- -
-- -------- - -------- -
----- - --------------- ----- - ---
-
-
-
------ ----------------
-这个例子展示了如何通过动态规划来解决最长递增子序列问题。理解这些基本概念和步骤后，你可以尝试应用它们来解决其他类型的问题。