使用场景
动态规划（Dynamic Programming）是一种算法思想，通常用于解决具有重叠子问题和最优子结构性质的问题，可以在优化时间复杂度的同时提高算法的效率。下面是动态规划的一些基本概念和应用场景。
- 重叠子问题：指在递归算法中，同一个子问题会被多次计算，造成算法效率低下。动态规划通过将子问题的解存储起来，避免了重复计算，提高了算法的效率。
- 最优子结构：指大问题的最优解可以由小问题的最优解推出。动态规划通过将大问题分解为小问题，并使用小问题的最优解来求解大问题的最优解。
- 状态转移方程：指将一个问题分解为若干个子问题，并通过子问题之间的关系来求解原问题的过程。状态转移方程是动态规划算法的核心，它描述了大问题和小问题之间的联系。
- 应用场景：动态规划算法广泛应用于各种领域，如计算机视觉、自然语言处理、机器人运动规划、游戏设计等。比较经典的动态规划问题包括背包问题、最长公共子序列问题、最长递增子序列问题等。
核心思想
动态规划算法的核心思想是将大问题分解为若干个子问题，并使用子问题的最优解来求解原问题的过程。具体来说，动态规划算法通常采用以下几个步骤：
- 定义状态：将原问题分解为若干个子问题，并定义子问题的状态，通常包括状态的含义和状态之间的关系。
- 状态转移方程：通过子问题之间的关系来推导状态转移方程，即大问题的解可以由子问题的解递推得出。
- 初始状态：确定初始状态，即问题规模最小的状态的解，通常为问题规模为1时的解。
- 计算顺序：确定计算顺序，通常采用自底向上的方式，先求解规模较小的子问题，再通过状态转移方程逐步求解规模较大的问题。
- 最优解：通过计算得到最优解，通常是最终状态的解。
动态规划算法的优点在于可以避免重复计算，提高算法的效率。然而，动态规划算法的时间和空间复杂度通常较高，需要针对具体问题进行优化。优化的方法包括记忆化搜索、滚动数组等。
示例
下面给出两个常见的动态规划问题的例子：
1. 最长递增子序列问题
最长递增子序列问题是指给定一个序列，找到其中一个最长的子序列，使得子序列中的元素单调递增。该问题可以使用动态规划算法求解。
状态定义：定义 dp[i] 为以第 i 个元素为结尾的最长递增子序列长度。
状态转移方程：dp[i] = max{1, dp[j]+1}，其中 j < i 且 a[j] < a[i]，表示在前 i-1 个元素中，以第 j 个元素结尾的最长递增子序列长度加上第 i 个元素，可以得到以第 i 个元素结尾的最长递增子序列长度。
初始状态：dp[i] = 1，表示以第 i 个元素结尾的最长递增子序列长度最小为 1。
计算顺序：自底向上计算 dp[i]，从小到大依次求解。
最优解：最长递增子序列的长度为 dp[i] 中的最大值。
2. 背包问题
背包问题是指有一个背包，可以装载一定的物品，每个物品有自己的价值和重量，要求在不超过背包容量的前提下，选取一些物品装入背包，使得装入的物品价值最大。该问题也可以使用动态规划算法求解。
状态定义：定义 dp[i][j] 为在前 i 个物品中，背包容量为 j 时的最大价值。
状态转移方程：dp[i][j] = max{dp[i-1][j], dp[i-1][j-w[i]]+v[i]}，其中 w[i] 为第 i 个物品的重量，v[i] 为第 i 个物品的价值，表示在前 i-1 个物品中，不装第 i 个物品的最大价值和在前 i-1 个物品中，装第 i 个物品的最大价值加上第 i 个物品的价值的较大值。
初始状态：dp[i][0] = dp[0][j] = 0，表示背包容量为 0 或没有物品时的最大价值为 0。
计算顺序：自底向上计算 dp[i][j]，从小到大依次求解。
最优解：在 dp[n][m] 中找到最大值，即为背包容量为 m 时的最大价值。
