动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学等领域中使用的优化方法。它主要用于求解具有重叠子问题和最优子结构性质的问题。

动态规划的核心思想是将复杂问题分解为一系列相互重叠的子问题，并按照一定的顺序求解子问题，将每个子问题的解存储起来以避免重复计算，最终得到原问题的解。

基本要素

阶段：将问题分解成若干个相互联系的阶段。每个阶段代表问题的一个步骤或子问题。
状态：在每一个阶段，问题所处的某种具体情形称为状态。状态通常可以用一个或多个变量来表示。
决策：在每一个阶段，根据当前状态做出选择或决策，以确定下一阶段的状态。
状态转移方程：描述如何从一个阶段的状态转移到下一个阶段的状态的数学方程。
边界条件：问题的初始状态或终结状态，它们是递推关系的起点和终点。

核心概念

多阶段决策问题

多阶段决策过程是指一个过程可以被划分成一系列阶段，每个阶段都需要做出决策。这些决策不仅影响当前阶段的结果，还会决定下一阶段的状态。这个过程是按照时间或空间的顺序逐步展开的。

在每个阶段，我们面对的是一组可能的状态，并基于当前状态选择一个行动，这将引导我们进入下一个阶段的新状态。整个决策过程的目标是从所有可能的决策序列中找出最优解。

例如，在爬楼梯问题中，每一阶楼梯代表一个阶段，每次可以选择上一阶或两阶楼梯，最终目标是找出到达楼顶的所有可能路径中最优的一种。

重叠子问题

在解决多阶段决策问题时，我们常常会遇到重叠子问题，即相同的子问题会在不同的阶段重复出现。如果不采用记忆化技术，这些子问题将不得不被重复计算。记忆化技术，或称为缓存，通过保存已解决子问题的结果，避免了重复计算，从而提高了效率。

例如，在递归求解过程斐波那契数列中，许多子问题（如 F(n-2) 和 F(n-3)）被重复计算多次。

无后效性

无后效性是动态规划中的一个关键概念，它表明一旦某个阶段的状态确定，后续阶段的决策和结果将不会受到之前决策的影响。这一特性简化了问题分析，因为我们不需要追踪整个决策路径，只需关注当前状态和未来的决策。

无后效性允许我们独立地考虑每个阶段的问题，并基于当前状态直接确定下一步的最佳行动。

例如，在背包问题中，当决定是否装入某个物品时，只需考虑当前剩余容量下的最大价值，而无需考虑之前是如何达到这种状态的。

最优子结构

最优子结构性质指的是，一个问题的最优解可以由其子问题的最优解组合而成。为了找到原问题的最优解，我们只需分别求解每个子问题的最优解，并据此构建出原问题的解。

这一性质成立的条件是子问题必须是相互独立的，或者至少它们之间的依赖关系是清晰可处理的。解决方案可以通过递归或迭代的方式构建，从最小的子问题开始，逐步扩展到整个问题。

例子：

在最短路径问题中，从A点到B点的最短路径包含的任何一段路径，也是从该段路径的起点到终点的最短路径。
在背包问题中，决定是否将某个物品装入背包时，考虑的是在剩余容量下的最大价值问题，这也是一个具有最优子结构的子问题。

样例介绍

最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

问题分析

最长递增子序列问题体现了动态规划的核心思想，特别是最优子结构性质。

对于示例中的最长递增子序列 [2,3,7,101]，可以认为它是由子数组 [10,9,2,5,3,7] 的最长递增子序列 [2,3,7] 增加一个 101 得到的。这说明当前问题的最优解可以通过其子问题的最优解经过决策后得到。

但是，并不是任何子问题的最优解都能直接推导出当前问题的最优解。关键在于如何从子问题的最优解中做出决策，以得到当前问题的最优解。

解题思路

我们定义 f[i] 为以 nums[i] 结尾的最长递增子序列的长度。在计算 f[i] 时，我们假设 f[0] 到 f[i-1] 已经被计算出来。

初始化：每个单独的数字本身构成一个长度为 1 的递增子序列，所以 f[i] 初始化为 1。
状态转移：对于每一个 i，枚举所有 j < i 且 nums[j] < nums[i] 的情况，更新 f[i] 为 f[j] + 1 的最大值。
结果：最终答案是 f 数组中的最大值。

c++

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0; // 如果数组为空，返回0

        int[] f = new int[n];
        Arrays.fill(f, 1); // 初始化，单独一个数字时长度是1
        int ans = 1; // 初始化答案为1，因为至少有一个元素

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) { // 满足递增子序列的要求
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            ans = Math.max(ans, f[i]); // 更新全局最长子序列长度
        }

        return ans;
    }
}

动态规划的高效性在于它只维护最优解，而不是穷举所有可能的子序列。这种方式相当于进行了剪枝，排除了许多不必要的“劣质解”。从子问题的最优解中枚举，确保了每次求解的都是当前问题的最优解。

基本要素 ​

核心概念 ​

多阶段决策问题 ​

重叠子问题 ​

无后效性 ​

最优子结构 ​

样例介绍 ​

问题分析 ​

解题思路 ​